CODEWITHSUNDEEP
pythonrecursionreturn
Ahnaf
Ahnaf

Reputation: 125

Recursion in depth (Python)

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.

Upvotes: 2

Views: 142

Answers (3)

Copperfield
Copperfield

Reputation: 8510

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

Upvotes: 5

Efferalgan
Efferalgan

Reputation: 1701

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 :

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

Upvotes: 3

Robert Columbia
Robert Columbia

Reputation: 6408

@MorganThrapp is correct. More specifically, the base case of the recursive function fib is:

if x==0 or x==1:
    return 1

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

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

Upvotes: 2

Related Questions