Interview Problem Explained: Fibonacci Number (LeetCode 509, DP & Memoization)

Fibonacci Number: Problem Statement

The Fibonacci sequence is defined as follows:

• F(0) = 0

• F(1) = 1

• F(n) = F(n − 1) + F(n − 2), for n > 1

The task is to calculate the n-th Fibonacci number F(n) for a given integer n.

Problem Requirements

1. Input: A single integer n such that 0 ≤ n ≤ 30

2. Output: Return the n-th Fibonacci number F(n)

Tip: This problem corresponds to LeetCode Problem #509.

While LeetCode’s description may be concise, Codetree provides deeper insights and examples to help you fully understand the problem.

Step 1. Naive Approach

Idea

The Fibonacci definition is recursive: F(n) = F(n − 1) + F(n − 2).

So, the most direct and intuitive approach is to write a recursive function that mirrors this definition. This is known as the naive recursive or pure recursive method.

Logic Breakdown

Here’s how we can structure the naive recursive approach to compute F(n):

1. Base Cases: Define the stopping conditions for recursion.

   • If n == 0, return 0.

   • If n == 1, return 1.

2. Recursive Case: For n > 1, proceed as follows:

• Recursively call  F(n - 1)to compute  F(n - 1).

• Recursively call F(n - 2) to compute F(n - 2).

1. Return Result: Return the sum of the two recursive calls as F(n).

Code Implementation

def F(n: int) -> int:
    # 1. Base cases (when n is 0 or 1)
    if n == 0:
        return 0
    if n == 1:
        return 1

    # 2, 3. Recursively compute F(n-1) and F(n-2) and return their sum
    return F(n - 1) + F(n - 2)

Time & Space Complexity Analysis

• Time Complexity: O(2^N). To compute F(n), you call both F(n - 1) and F(n - 2), and this process repeats recursively. This forms a binary tree of height N, where each node spawns two child calls. The total number of calls is roughly proportional to 2^N. For N ≥ 30, 2^30 is about 10^9, which is extremely large and will likely result in a time limit exceeded error or severe inefficiency.

• Space Complexity: O(N). The maximum depth of the call stack is proportional to N, as the recursion can go from F(n) down to  F(0) or F(1) stacking up to N  function calls.

Step 2. Memoization

Idea

The naive approach in Step 1, i.e.,F(5), F(3), F(2), suffers from severe inefficiency due to repeated calculations for the same n.

For example, consider the computation of  F(5):

F(5)
├─ F(4)
│  ├─ F(3)
│  │  ├─ F(2)
│  │  │  ├─ F(1)   (base case)
│  │  │  └─ F(0)   (base case)
│  │  └─ F(1)       ← F(1) recalculated
│  └─ F(2)          ← F(2) recalculated (includes F(1), F(0))
│     ├─ F(1)
│     └─ F(0)
└─ F(3)              ← F(3) recalculated (includes F(2), F(1))
   └ ... (internally, F(2), F(1), F(0) are recalculated)

As shown, F(3), F(2), F(1), etc., are computed multiple times. Since the Fibonacci value for each n is uniquely determined, repeated computation for the same n is wasteful.

This structure of "overlapping subproblems" is a key indicator that memoization can be applied. Memoization is a technique where you store the results of subproblems and immediately return the stored result when the same subproblem is encountered again, avoiding redundant work.

Logic Breakdown

A memoized Fibonacci function can be structured as follows:

1. Prepare a storage (typically a dictionary or an array—here we use a memo dictionary), and pre-store the base cases: F(0) = 0, F(1) = 1

2. When F(n) is called, first check if the result for n is already in memo.

▪️ If it exists: Return the stored value immediately — no computation needed.

▪️ If it doesn’t exist:

a. Recursively compute F(n - 1) and F(n - 2) using the same function.

b. Add the two results to get F(n).

c. Store the computed result in memo with n as the key.

d. Return F(n).

Memoization Example for F(5)

As a result, each F(k) (for k = 0, 1, 2, 3, 4, 5) is computed only once and stored in memo. Any subsequent call for the same k retrieves the value instantly. For F(5), naive recursion executes the function 15 times, but with memoization, each n (from 0 to 5) is computed only once, resulting in just 6 main calculations.

This technique of storing and reusing previously computed results is a form of dynamic programming (specifically, the top-down approach)

Code Implementation

Memoization

# Prepare memo (dictionary) to store results
# Pre-store base cases
memo = {0: 0, 1: 1}

def fib_memo(n: int) -> int:
    """
    Fibonacci function with memoization (Top-down DP)
    1. Check if result for n is already in memo; if so, return it immediately.
    2. If not, recursively compute and store the result in memo before returning.
    """
    if n in memo:  # If already computed, use it
        return memo[n]

    # If not computed, recursively calculate and store in memo
    result = fib_memo(n - 1) + fib_memo(n - 2)
    memo[n] = result
    return result

Time and Space Complexity

• Time Complexity: O(N). Each call to fib(k) (where k ranges from 0 to N) performs actual computation only once and stores the result in the memo. For any subsequent call to the same k, the value is retrieved from the memo in O(1) time. Since there are N + 1 subproblems (from F(0) to F(N)), each computed only once, the total time complexity is O(N). Each addition operation takes constant time.

• Space Complexity: O(N). Due to recursion, the maximum call stack depth can reach up to N. Additionally, the memo dictionary (or an array) stores N + 1 results. Hence, the total space complexity is O(N), accounting for both recursion stack and memoization storage.

Frequently Asked Questions

Q: Why does the naive recursive approach for Fibonacci result in poor performance?

A: Because it repeatedly recalculates the same values (e.g., F(2)), causing exponential growth in function calls.

Q: What is memoization, and how does it help in the Fibonacci problem?

A: Memoization stores previously computed results so that repeated subproblems return cached values instantly, avoiding redundant calculations.

Q: What is the time complexity when memoization is used for Fibonacci?

A: Since each Fibonacci value (F(0) through F(n)) is computed only once, the time complexity is improved to O(N).

Q: Is it possible to solve the Fibonacci problem without recursion?

A: Yes. You can use Tabulation or a Bottom-up DP approach, which computes values from F(0) and F(1) up to F(N) using iteration.

How to Prepare for Interviews with the “Fibonacci Number” Problem

The Fibonacci Number problem is a classic interview question that evaluates your understanding of recursion and dynamic programming. Interviewers use it to assess whether you can identify inefficient patterns and optimise them effectively using memoization and tabulation.

This problem helps you develop:

• Understanding and implementing recursive logic

• Applying memoization to eliminate redundant calculations

• Mastering the fundamentals of Dynamic Programming

Similar Problems to Practice

• Climbing Stairs

• N-th Tribonacci Number

• Rectangle Fill (Codetree)

These problems share core dynamic programming concepts and optimisation strategies.

How to review after solving this problem:

1. Identify the core pattern: Understand the structure of problems where the current value is calculated using previous values (often defined by recurrence relations), and explore other problems with similar logic.

2. Summarise in one sentence: For example, “Implement the recurrence relation of the Fibonacci sequence with memoization to remove duplicate calculations.”

3. Compare and apply: Examine how the idea of recurrence + memoization is similarly or differently used in related DP problems like stair climbing or tile filling.