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>@MorganThrapp is correct. More specifically, the base case of the recursive function <code>fib</code> is:</p>

<pre><code>if x==0 or x==1:
    return 1
</code></pre>

<p>This clause is triggered when <code>fib(1)</code> or <code>fib(0)</code> is called. In programming parlance, the function <em>evaluates</em> to its return value, which here is <code>1</code>.</p>

<p>In your example of <code>fib(4)</code>, <code>fib</code> gets called five times with either a <code>1</code> or a <code>0</code> input and those results are all added together, and that results in your final return value of <code>5</code> which is returned from your original call to <code>fib(4)</code> and immediately passed into the <code>print</code> function.</p>

python recursion return