Fibonacci Number

Q: What is the time complexity of the recursive Fibonacci function?

The naive recursion makes 2 × F(n+1) - 1 calls, a count that grows like 1.618^n and is usually written O(2^n) . Storing each result once, in a table or in two variables, brings it down to O(n) .

Q: Why does the recursive Fibonacci use only O(n) space?

Only one chain of calls is on the stack at a time, and the deepest chain runs n , n-1 , down to 1. A call frees its frame when it returns, so the stack never holds more than n frames, even though the total number of calls is exponential.

Q: How do you solve Fibonacci with dynamic programming?

Compute the values in increasing order of n and store each one, in a table filled from the bottom up. Or keep the recursive function and cache its results, which is called memoization. Either way each value is computed once, so the work is O(n) .

BeginnerDynamic programming Recursion

+10

The Fibonacci numbers start with F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n-1) + F(n-2). The sequence begins 0, 1, 1, 2, 3, 5, 8, 13. Your function gets n and returns F(n).

Function

fib(n: integer) → integer

ninteger: the position in the Fibonacci sequence, counting from 0
Returnsinteger: the Fibonacci number F(n)

Constraints

0 ≤ n ≤ 45
The answer fits in a signed 32-bit integer: F(45) = 1134903170.

Examples

Input: n = 4
Output: 3
Explanation: Count up from the start: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, and F(4) = 2 + 1 = 3.

Input: n = 10
Output: 55
Explanation: The sequence from index 0 runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. The number at index 10 is 34 + 21 = 55.

Follow-up

Can you compute F(n) in O(log n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The definition is already a recursive function, and coding it as one gives the right answer in exponential time, because the two calls redo each other's work. Dynamic programming computes each number once, from the bottom up. Each number needs only the two before it, so two variables are enough.

Recursion straight from the definition

Correct, but does not finish on the largest tests

Intuition

Translate the definition: return fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. Every chain of calls ends in a base case, so the answer is right.

The calls repeat work. fib(5) runs fib(3) twice, fib(2) three times and fib(1) five times, 15 calls in all. In general F(n) takes 2 × F(n+1) - 1 calls, about 3.7 × 10^9 at n = 45. The count grows like 1.618^n, usually written O(2^n). The stack is n levels deep, so the space is O(n).

Algorithm

If n is 0 or 1, return n.
Otherwise call the function on n-1 and on n-2.
Return the sum of the two results.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Fill a table from the bottom up

Intuition

The recursion is slow because it forgets. Write each number down the first time you compute it, and each one costs a single addition. Fill the table from left to right: when you reach f[i], both values it needs are already there. For n = 10 the table reads 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

That is n-1 additions, O(n) time, and n + 1 slots, O(n) space. n = 45 takes 44 additions instead of billions of calls.

Algorithm

If n is 0 or 1, return n.
Create a table of n + 1 numbers with f[0] = 0 and f[1] = 1.
For i from 2 to n, set f[i] = f[i-1] + f[i-2].
Return f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Keep only the last two numbers

Intuition

Filling f[i] reads only f[i-1] and f[i-2], so every older slot is dead weight. Keep two variables: prev, the number two steps back, and curr, the number one step back. For n = 4 the pair moves from (0, 1) to (1, 1), (1, 2) and (2, 3), and curr = 3 is the answer.

The work is the same n-1 additions, O(n) time, in O(1) space.

Algorithm

If n is 0 or 1, return n.
Set prev = 0 and curr = 1.
Repeat n-1 times: compute next = prev + curr, then set prev = curr and curr = next.
Return curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Pitfalls and edge cases

Handing in the naive recursion. It is correct, but it makes billions of calls at n = 45.
Starting the sequence at 1, 1. Here F(0) = 0, so F(10) is 55, not 89.
No guard for small n in the table version. For n = 0 the table has one slot, so writing f[1] is out of bounds. Return n when n < 2.
Updating the pair in the wrong order. prev = curr followed by curr = prev + curr doubles curr on every step, so n = 4 returns 8. Compute next first, or use a simultaneous assignment.

Frequently asked questions3

What is the time complexity of the recursive Fibonacci function?

The naive recursion makes 2 × F(n+1) - 1 calls, a count that grows like 1.618^n and is usually written O(2^n). Storing each result once, in a table or in two variables, brings it down to O(n).

Why does the recursive Fibonacci use only O(n) space?

Only one chain of calls is on the stack at a time, and the deepest chain runs n, n-1, down to 1. A call frees its frame when it returns, so the stack never holds more than n frames, even though the total number of calls is exponential.

How do you solve Fibonacci with dynamic programming?

Compute the values in increasing order of n and store each one, in a table filled from the bottom up. Or keep the recursive function and cache its results, which is called memoization. Either way each value is computed once, so the work is O(n).