Recursive function help Python

Question

Input:
def fb(n):
if n==0:
return 0
if n == 1:
return 1
else:
return(fb(n-1)+ fb(n-2))
print (fb(5))

Output:

5

This makes my brain sad. Why is this 5?

Answer 1

The recursive implementation of the Fibunacci Sequence - a true classic!
Precisely, this code returns the n-th Fibunacci number (in this case, the 5th)

By default, the Fibunacci sequence starts with 0 and 1.
Each Fibunacci number n is the sum of its two predecessors (n-1) and (n-2).

Let's move our way up to fb(n) where n = 5:

n = 0 -> return 0 --- 0
n = 1 -> returns 1 ---- 0 1
n = 2 -> returns: n-1 (= 1) + n-2 (=0) -> 1 --- 0 1 1
n = 3 -> returns: n-1 (= 1) + n-2 (=1) -> 2 --- 0 1 1 2
n = 4 -> returns: n-1 (= 2) + n-2 (=1) -> 3 --- 0 1 1 2 3
n = 5 -> returns: n-1 (= 3) + n-2 (=2) -> 5 --- 0 1 1 2 3 5

In other words: each n-th iteration returns the sum of
1. the value of the previous ITERATION (n-1) and
2. the value of the pre-previous iteration (n-2)

In other words: n-1 IS NOT 4 and n-2 IS NOT 3!!

Losely speaking: n-1 is the 4th ITERATION of the FUNCTION
and n-2 is the 3rd ITERATION of the FUNCTION.

It took me a looooong time to get this, and I still struggle at times to get the code right.
However, recursion is a core-concept in many programming languages and worth studying.
Don't be sad - just keep practicing!

To get the entire sequence instead of the n-th number, substitute "print(fb(5))" with

for n in range(6):
print(fb(n))

This will print you all the values from 0 - 5

Answer 2

1. f(4) + f(3)
2. f(3) + f(2) f(2) + 1
3. f(2)+1+ 1+0 1 + 0
4. 1+0
=> five paths end with 1

Answer 3

See this post.

https://www.sololearn.com/discuss/1149517/?ref=app

Answer 4

Thank you!! I needed to hear that! So is it best practice to start from the bottom up?