Why Dynamic Programming and When Recursion Alone Fails in DSA Python - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Without Memoization

What is the output of the following code snippet when calling fib(5)?

DSA Python

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

print(fib(5))

A 13

B 8

C 5

D 3

💡 Hint

Trace the calls fib(5) = fib(4) + fib(3) and so on.

The recursive Fibonacci function returns the 5th Fibonacci number, which is 5.

❓ Predict Output

intermediate

Output of Recursive Fibonacci With Memoization

What is the output of the following code snippet when calling fib(5)?

DSA Python

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

A 5

B 8

C 13

D TypeError

💡 Hint

Memoization stores results to avoid repeated calculations.

Memoization optimizes recursion by storing results. fib(5) returns 5.

🧠 Conceptual

advanced

Why Pure Recursion Can Be Inefficient

Why can pure recursion without memoization be inefficient for problems like Fibonacci?

A Because recursion always uses more memory than iteration.

B Because recursion does not allow base cases.

C Because recursion cannot solve problems with overlapping subproblems.

D Because it repeats calculations for the same inputs multiple times, causing exponential time complexity.

💡 Hint

Think about how many times fib(3) is calculated in fib(5) without memoization.

Pure recursion repeats the same calculations many times, leading to slow performance.

🧠 Conceptual

advanced

When to Use Dynamic Programming Instead of Recursion

In which situation is dynamic programming preferred over plain recursion?

A When the problem has no base case and infinite recursion occurs.

B When the problem has overlapping subproblems and optimal substructure, so caching results avoids repeated work.

C When recursion depth is very shallow and performance is not a concern.

D When the problem cannot be broken down into smaller subproblems.

💡 Hint

Dynamic programming stores results to reuse them efficiently.

Dynamic programming is best when subproblems overlap and results can be reused to save time.

🔧 Debug

expert

Identify the Error in Recursive Fibonacci with Mutable Default Argument

What error or unexpected behavior occurs when running this code and why?

DSA Python

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))
print(fib(6))

A The second call fib(6) uses the same memo dictionary from the first call, causing unexpected results.

B The code raises a SyntaxError due to mutable default argument.

C No error; the code runs correctly and prints 5 and 8.

D The code raises a TypeError because memo is not passed correctly.

💡 Hint

Consider what happens to the default argument memo between calls.

Using a mutable default argument causes the memo dictionary to persist between calls, which can lead to unexpected behavior.

Practice

1. Why do we use dynamic programming instead of just recursion for some problems?

easy

A. Because recursion cannot solve problems with multiple steps.

B. Because recursion always causes errors in large problems.

C. Because dynamic programming uses loops instead of functions.

D. Because recursion alone can repeat the same calculations many times, making it slow.

Solution

1. Step 1: Understand recursion's limitation

   Recursion solves problems by calling itself but often recalculates the same results multiple times.

2. Step 2: How dynamic programming helps

   Dynamic programming stores results of subproblems to avoid repeated work, making it faster.

3. Final Answer:

   Because recursion alone can repeat the same calculations many times, making it slow. -> Option D

4. Quick Check:

   Recursion repeats work = use DP [OK]

Hint: Recursion repeats work; DP saves results to speed up [OK]

Common Mistakes:

• Thinking recursion can't solve multi-step problems
• Believing DP only uses loops, not recursion
• Assuming recursion always causes errors

2. Which of the following is the correct way to define a memoization dictionary in Python for dynamic programming?

easy

A. memo = {}

B. memo = []

C. memo = ()

D. memo = set()

Solution

1. Step 1: Identify the data structure for memoization

   Memoization stores key-value pairs of subproblem results, so a dictionary is suitable.

2. Step 2: Match syntax to dictionary

   In Python, dictionaries are defined with curly braces {}, so memo = {} is correct.

3. Final Answer:

   memo = {} -> Option A

4. Quick Check:

   Memoization uses dictionary = {} [OK]

Hint: Use {} for memo dictionary in Python [OK]

Common Mistakes:

• Using list [] which is ordered but not key-value
• Using tuple () which is immutable
• Using set() which stores only unique values without keys

3. What will be the output of this Python code snippet?

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

medium

A. 3

B. 8

C. 5

D. Error

Solution

1. Step 1: Understand the Fibonacci function with memoization

   The function returns Fibonacci numbers using memo to save results and avoid repeated calls.

2. Step 2: Calculate fib(5) step-by-step

   fib(5) = fib(4) + fib(3), fib(4) = 3, fib(3) = 2, so fib(5) = 3 + 2 = 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Memoized fib(5) = 5 by adding fib(4) + fib(3) [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memo and recalculating
• Expecting error due to mutable default argument

4. Find the error in this recursive Fibonacci function and choose the correct fix:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-3)

medium

A. Add memoization dictionary to store results.

B. Change fib(n-3) to fib(n-2) to correctly sum previous two Fibonacci numbers.

C. Change base case n==0 to n<=0.

D. No error; function works correctly.

Solution

1. Step 1: Identify the recursive calls

   The function calls fib(n-1) and fib(n-3), but Fibonacci sums fib(n-1) and fib(n-2).

2. Step 2: Correct the recursive call

   Change fib(n-3) to fib(n-2) to follow Fibonacci definition properly.

3. Final Answer:

   Change fib(n-3) to fib(n-2) to correctly sum previous two Fibonacci numbers. -> Option B

4. Quick Check:

   Fibonacci sums fib(n-1) + fib(n-2) [OK]

Hint: Fibonacci sums previous two, not previous and third previous [OK]

Common Mistakes:

• Using wrong recursive calls like fib(n-3)
• Ignoring base cases
• Assuming no error in recursion

5. You want to find the number of ways to climb a staircase of 4 steps, taking 1 or 2 steps at a time. Which approach best avoids repeated calculations and why?

def climb(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    memo[n] = climb(n-1, memo) + climb(n-2, memo)
    return memo[n]

print(climb(4))

hard

A. Using dynamic programming with memoization to store and reuse results.

B. Using recursion but only calling climb(n-1) once.

C. Using a loop without storing previous results.

D. Using recursion alone without memoization, which repeats calculations.

Solution

1. Step 1: Understand the problem and code

   The function counts ways to climb stairs using recursion with memoization to save results.

2. Step 2: Why memoization helps

   Memoization avoids recalculating climb(n-1) and climb(n-2) multiple times, improving efficiency.

3. Final Answer:

   Using dynamic programming with memoization to store and reuse results. -> Option A

4. Quick Check:

   Memoization saves repeated work = DP [OK]

Hint: Memoize recursive calls to avoid repeated work [OK]

Common Mistakes:

• Using recursion without memoization causing slow code
• Using loops without storing previous results
• Calling only one recursive branch