Recursion on Fibonacci Sequence

Question

I need some help in understanding the processing that happens here, so let´s say I call fib(5) I want the fibonacci 5, which is 8. But my brain in trying to understand the algorithm says it´s not. This is how i (wrongly) think:

return fib(4) + fib(3) // Stack frame 1
return fib(3) + fib(1) // Stack frame 2

now cause x is 1 fib(1), the conditional statement if x == 0 or x == 1: causes the recursion to end. Which according to my logic would become 3+1+4+3. Please correct my faulty logic.

def fib(x):
    """assumes x an int >= 0
       returns Fibonacci of x"""
    assert type(x) == int and x >= 0
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

Just write down on a paper the first call and replace each recursive calls of the function with the valid return statement. What you probably don't understand is that return fib(x - 1) + fib( x - 2) calls twice your fib function, one with parameter x = current x decremented once, and the other decremented twice. You should also probably look into function arguments again, since this is a typical misunderstanding when using functions (at first). — Jean-Marie Comets
– Jean-Marie Comets, Commented Dec 1, 2012 at 10:36
Just put some print statement in your function and run it to see what it's doing. — martineau
– martineau, Commented Dec 1, 2012 at 10:38

NPE · Accepted Answer · 2012-12-01 10:36:56Z

6

Here is the full expansion of what happens:

fib(5) expands to fib(4)+fib(3)
  fib(4) expands to fib(3)+fib(2)
    fib(3) expands to fib(2)+fib(1)
      fib(2) expands to fib(1)+fib(0)
        fib(1) evaluates to 1
        fib(0) evaluates to 1
      fib(1) evaluates to 1
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
  fib(3) expands to fib(2)+fib(1)
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
    fib(1) evaluates to 1

If you count the ones, you get 8 as the answer.

answered Dec 1, 2012 at 10:36

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Martijn Pieters · Accepted Answer · 2012-12-01 10:37:00Z

6

For all x greater than 1, the fib function calls itself twice:

fib(5) becomes fib(4) + fib(3)
and expands to (fib(3) + fib(2)) + (fib(2) + fib(1))
and expands to ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
expands to (((fib(1) + fib(0)) + 1) + (1 + 1)) + ((1 + 1) + 1)
expands to (((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

which sums up to 8.

answered Dec 1, 2012 at 10:37

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Comments

bterwijn · Accepted Answer · 2025-04-09 02:05:36Z

You can use package invocation_tree to visualize the execution:

import invocation_tree as ivt  # see link above for install instructions

def fib(x):
    """assumes x an int >= 0
       returns Fibonacci of x"""
    assert type(x) == int and x >= 0
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

tree = ivt.blocking()  # blocks execution and waits for <Enter> key press
print( tree(fib, 5) )

As you can see that a lot of duplicate computations are performed. To speed things up you can cache the input and output of each function call so that when the the functions is called with the same input the matching output gets reused so that no computation is required.

import invocation_tree as ivt
from functools import cache

@cache
def fib(x):
    """assumes x an int >= 0
       returns Fibonacci of x"""
    assert type(x) == int and x >= 0
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

tree = ivt.gif("fib.png")
print( tree(fib, 5) )

This technique is called memoization and can significantly improve performance.

Full disclosure: I am the developer of invocation_tree.

Collectives™ on Stack Overflow

Recursion on Fibonacci Sequence

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related