Finding Fibonacci of a number using recursion method

Question

Is it a bad idea to use recursion method to find the fibonacci of a number? If yes/no support answer with reasons

Answer 1

Pardon my Python (not to mention my neglecting of the case $n<0$).

If this question means what I think it does, the point is that e.g. def fibonacci(n): return n if n<2 else fibonacci(n-2)+fibonacci(n-1) runs in exponential time, whereas

def fibonacci(n):
    if n<2: return n
    a, b = 1, 1
    for i in range(n-2): a, b = b, a+b
    return b

is much more efficient. There are other subexponential approaches, too, such as one using $F_{2n-1}=F_{n-1}^2+F_n^2,\,F_{2n}=F_n(F_n+2F_{n-1})$.