Recursion in depth (Python)
<p>Check the following code:</p>

<pre><code>&gt;&gt;&gt; def fib(x):
...    if x == 0 or x == 1:
...        return 1
...    else: 
...        return fib(x-1) + fib(x-2)
&gt;&gt;&gt; print(fib(4))
</code></pre>

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

<pre><code>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
</code></pre>

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

<p>Do forgive me for asking such a noob question.</p>

<p>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)</p>

<pre><code>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
</code></pre>

<p>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</p>

<pre><code>&gt;&gt;&gt; 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

&gt;&gt;&gt; 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
&gt;&gt;&gt; 
</code></pre>

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

python recursion return