Recursion in depth (Python)

Question

Check the following code:

>>> def fib(x):
...    if x == 0 or x == 1:
...        return 1
...    else: 
...        return fib(x-1) + fib(x-2)
>>> print(fib(4))

According to the comments in the SoloLearn Python tutorial (for Recursion), the code works like this:

1. fib(4) = fib(3) + fib(2)
2. = (fib(2) + fib(1)) + (fib(1) + fib(0))
3. = fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
4. = 1+ 1 + 1 + 1 + 1
5. = 5

After line 2, only fib(2) should go the else part of the fib() function, right? The two fib(1) and the single fib(0) meet the criteria of the if part of the fib() function. So 1 is returned. My question is, why in the 3rd line, fib(1) + fib(0) + fib(1) + fib(1) + fib(0) are all replaced by 1's and then added?

Do forgive me for asking such a noob question.

Answer 1

this is a double recursive function, so its call result a tree structure of calls with the base case of fib(1) and fib(0)

fib(4) =                  fib(3)          +        fib(2)    
                         /      \                 /     \
fib(4) =        (  fib(2)   +    fib(1) ) + ( fib(1) + fib(0) )    
                  /     \         |              |        |
fib(4) = ( ( fib(1) + fib(0) ) + fib(1) ) + ( fib(1) + fib(0) )    
               |        |          |            |        |
fib(4) = ( (   1    +   1    ) +   1    ) + (   1    +   1    )    
                  \   /            |               \    /
fib(4) = ( (        2        ) +   1    ) + (        2        )    
                        \       /                    |
fib(4) = (                  3           ) + (        2        )    
                                   \             /
fib(4) =                                  5

you can also visualize the working of the function by adding some prints in the right places and a extra auxiliary argument to aid with it and some other minor changes

>>> def fib(n, nivel=0):
        if n==0 or n==1:
            print(" "*nivel,"fib(",n,")=1")
            return 1
        else:
            print(" "*nivel,"fib(",n,")")
            result = fib(n-1,nivel+1) + fib(n-2,nivel+1)
            print(" "*nivel,"fib(",n,")=",result)
            return result

>>> fib(4)
 fib( 4 )
  fib( 3 )
   fib( 2 )
    fib( 1 )=1
    fib( 0 )=1
   fib( 2 )= 2
   fib( 1 )=1
  fib( 3 )= 3
  fib( 2 )
   fib( 1 )=1
   fib( 0 )=1
  fib( 2 )= 2
 fib( 4 )= 5
5
>>> 

here you can notice that the call are resolved in sequence from left to right and bottom up