Fibonacci Number

Difficulty: Easy

Problem

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

Example

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

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: If someone magically gives you F(n-1) and F(n-2), then F(n) = F(n-1) + F(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!

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. Approximately O(2^n) total calls. 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 F(5)?

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

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

F(4) = F(3) + F(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?

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

Related problems

Keep practising