# 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)```

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