I don't Understand Fibonacci

I don’t Understand this function at all. When I input 4 into it, I get out 3 but I dont see how
EDIT: Ok I think I figured it out. Only question now is, how is the run time 2^N?

def fibonacci(n):
  if n == 1:
    return 1
  if n == 0:
    return 0
  return fibonacci(n-1) + fibonacci(n-2)```



https://www.codecademy.com/paths/computer-science/tracks/learn-recursion-python/modules/recursion-python/lessons/recursion-python/exercises/recursion-python-fibbonacci
1 Like

Hey @jaccobtw

Let’s step through what’s happening.

The Fibonacci series is a sequence of numbers where each number is the sum of the two numbers previous. So, the sequence written out is 1,1,2,3,5,8,13...

fibonacci(1) returns 1, because n == 1 evaluates to True and so we return 1.
fibonacci(2) doesn’t result in either of your if statements evaluating to true, so we return fibonacci(1) + fibonacci(0). As we already know, fibonacci(1) = 1, and fibonacci(0) = 0. 1 + 0 = 1.

fibonacci(4) returns fibonacci(3) + fibonacci(2). fibonacci(3) returns fibonacci(2) + fibonacci(1), so fibonacci(4) is the same as (fibonacci(2) + fibonacci(1)) + fibonacci(2). We already know that fibonacci(2) = fibonacci(1) + fibonacci(0).

So, fibonacci(4) is the same as fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0), which evaluates to 1 + 0 + 1 + 1 + 0 = 3.

That’s probably horrendously unclear, but such is the joy of recursion.

2 Likes

To see how it takes 2^n time complexity, you must be able to convince yourself that it takes approximately fib(n) steps to complete. This is because it has to recreate all prior calculations: to get fib(n), you have to do fib(n-1) and fib(n-2), etc. If you draw a tree, you’ll see this.

It so happens that fib(n) is closely approximated by (1/sqrt(5)) * 1.618^(n+1), close enough to 2^n for “big-O” purposes. 1.618 is the so-called “golden ratio.”

The actual math to get from here to there is over my head, but is easily accessible on the internet, along with many verbal and graphical attempts at simplification.

2 Likes