Fibonacci Number

Difficulty: Easy

Problem

Picture a chart where every entry is the total of the two entries right before it. It starts with fib(0) = 0 and fib(1) = 1, so fib(n) = fib(n-1) + fib(n-2) whenever n > 1. Return fib(n) for the given n, using recursion. Here n is zero or more (n >= 0).

Example

Input: n = 7
Output: 13
Explanation: The sequence runs 0, 1, 1, 2, 3, 5, 8, 13, so fib(7) = fib(6) + fib(5) = 8 + 5 = 13.

Brute-force approach

The plain way is a loop: keep the last two values and add them, n - 1 additions in total (6 additions for n = 7). It is the comparison for the recursive version, which is slower but is the 'hello world' of recursive thinking.

Steps

  1. If n <= 1, return n
  2. Start with a = 0 and b = 1 (the values at positions 0 and 1)
  3. Repeat n - 1 times: new value = a + b, then slide a and b forward
  4. Return b

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Does not practise recursive thinking, which trees, choices and backtracking need

Optimal approach

Key insight: If someone magically gives you fib(n-1) and fib(n-2), then fib(n) = fib(n-1) + fib(n-2). That's it: trust the recursion!

Use the Leap of Faith recipe to build the recursive solution: identify the smaller problem, trust the recursive call, combine results, and add the base case.

Steps

  1. Base case: if n <= 1, return n
  2. Leap of Faith: trust that fib(n-1) and fib(n-2) return correct values
  3. Combine: return fib(n-1) + fib(n-2)

Time complexity: O(2^n) · Space complexity: O(n)

Pseudocode

function fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Hints

  • What is the simplest input where you already know the answer? (Base case)
  • If someone magically gave you fib(n-1) and fib(n-2), could you compute fib(n)?
  • Trust that the recursive calls work, that's the Leap of Faith!
  • fib(3) means the value at position 3 (the third term counting from 0), not a countdown from 3.
  • fib(2) needs fib(1) AND fib(0), so one base case is not enough: you need both fib(0) and fib(1).

Complexity questions

What is the time complexity of the recursive Fibonacci solution?

O(2^n). Each call branches into TWO more calls. The recursion tree has exponential nodes. The number of calls is exactly 2 * fib(n + 1) - 1 (1, 1, 3, 5, 9, 15, 25, 41 for n = 0 to 7). O(2^n) is an upper bound because each call makes two calls; the tight growth is about 1.618^n (the golden ratio), still exponential. This is expected for pure recursion; optimization belongs in the DP section.

What is the space complexity of the recursive Fibonacci solution?

O(n). The maximum recursion depth is n (the longest chain of calls before reaching a base case). Each call uses constant space on the stack, so total stack space is O(n).

How many times is fib(2) called when computing fib(5)?

3. fib(2) is called 3 times in the recursion tree. This redundancy is why pure recursion is O(2^n). Memoization (covered in DP) eliminates this by caching results.

Check your understanding of Fibonacci Number

What is fib(5)?

5. fib(5) = fib(4) + fib(3) = 3 + 2 = 5. The sequence: 0, 1, 1, 2, 3, 5.

If someone magically gives you fib(3)=2 and fib(2)=1, how do you compute fib(4)?

fib(4) = fib(3) + fib(2) = 3. That's the Leap of Faith! If you TRUST that fib(3)=2 and fib(2)=1 are correct, then fib(4) = 2 + 1 = 3. You don't need to trace into the recursive calls.

What are the base cases for Fibonacci?

fib(0) = 0 and fib(1) = 1. The two base cases are fib(0) = 0 and fib(1) = 1. These are the simplest inputs where we know the answer without any computation.

Related problems

Keep practising