I do not like this demonstration of recursion and it I think the only reason Fibonacci is used is because it is so much easier and more efficient when solved without using recursion.
How do you calculate Fibonacci numbers? The next number in the sequence is equal to the sum of the previous two numbers.
0, 1, (0 + 1), (1 + (0 + 1)), ((0 + 1) + (1 + (0 + 1)))
Using a list this is quite easy to do;
fibonacci = [0, 1]
while len(fibonacci) < 10:
fibonacci.append(fibonacci[-2] + fibonacci[-1])
print(fibonacci)
Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
But what how can you calculate the next number in the Fibonacci sequence if you don't have the list of previous numbers? You have to generate the list, and that is what the recursion is doing in your example. Let's expand Fibonacci(5):
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==0:
return 0
# Second Fibonacci number is 1
elif n==1:
return 1
else:
return Fibonacci(n-1)+Fibonacci(n-2)
Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
= (Fibonacci(3) + Fibonacci(2)) + Fibonacci(3)
= (Fibonacci(3) + (Fibonacci(1) + Fibonacci(0))) + Fibonacci(3)
= (Fibonacci(3) + (1 + 0)) + Fibonacci(3)
= (Fibonacci(3) + 1) + Fibonacci(3)
= ((Fibonacci(2) + Fibonacci(1)) + 1) + Fibonacci(3)
= ((Fibonacci(2) + 1) + 1) + Fibonacci(3)
= (((Fibonacci(1) + Fibonacci(0)) + 1) + 1) + Fibonacci(3)
= (((1 + 0) + 1) + 1) + Fibonacci(3)
= (3) + (Fibonacci(2) + Fibonacci(1))
= (3) + (Fibonacci(2) + 1)
= (3) + ((Fibonacci(1) + Fibonacci(0)) + 1)
= (3) + ((1 + 0) + 1)
= (3) + (2)
= 5
Hopefully this provides a better view of what the recursion is doing. If the input is 1 or 0, the result can be calculated immediately. If the input is greater than 1, the value is calculated by calling the function again using n-1 and n-2. To calculate Fibonacci(5) we need to calculate Fibonacci(4) and Fibonacci(3). To calculate Fibonacci(3) we need to calculate Fibonacci(2) and Fibonacci(1). To calculate Fibonacci(2) we need to calculate Fibonacci(1) and Fibonacci(0). Fibonacci(1) and Fibonacci(0) can be calculated directly.
Maybe it is easier to think of the problem like this:
def Fibonacci2():
return 1 + 0
def Fibonacci3():
return Fibonacci2() + 1
def Fibonacci4():
return Fibonacci3() + Fibonacci2()
def Fibonacci5():
return Fibonacci4() + Fibonacci3()
print(Fibonacci5())
Here the recursion is replaced by giving each number it's own function. Though it looks slightly different, what it does is the same. The only difference is the recursive solution uses the same Fibonacci(N) in place of FibonacciN.
Not all languages support recursion, though nearly all modern programming languages do. FORTRAN and COBOL are two historically important languages that use statically allocated variables instead of a stack. These languages cannot call a function recursively because there is no place to store the intermediate results.