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>I believe the description of how the code works is misleading, since it seems to show that not every values are evaluated when going from one line to the next. If we replace everything by the functions it calls (or the value it returns) on the next line, and put parentheses like on your example, we get the following, that might help you understand better the inner workings of that code :</p>

<pre><code>1. fib(4) 
2. = fib(3) + fib(2)
3. = (fib(2) + fib(1)) + (fib(1) + fib(0))
4. = ((fib(1) + fib(0)) + 1) + (1 + 1)
5. = 1 + 1 + 1 + 2
6. = 5
</code></pre>

python recursion return