Why Dynamic Programming and When Recursion Alone Fails in DSA Python - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci numbers using simple recursion.

DSA Python

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

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting base cases leading to infinite recursion.

The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2). So the operator must be '+'.

2fill in blank

medium

Complete the code to store computed Fibonacci values in a cache dictionary.

DSA Python

def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n-1, cache) [1] fib_memo(n-2, cache)
    return cache[n]

Drag options to blanks, or click blank then click option'

A//

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Not using the cache leading to slow performance.

Using wrong operators causing incorrect results.

Memoization stores results of fib(n-1) + fib(n-2) to avoid repeated calculations.

3fill in blank

hard

Fix the error in the recursive Fibonacci function that causes repeated calculations.

DSA Python

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

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Changing the operator instead of adding caching.

Ignoring the exponential time complexity of naive recursion.

The error is not an operator but the lack of caching. The operator '+' is correct but repeated calls cause inefficiency.

4fill in blank

hard

Fill both blanks to create a bottom-up dynamic programming solution for Fibonacci.

DSA Python

def fib_dp(n):
    dp = [0, 1] + [0] * (n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] [1] dp[i-2]
    return dp[[2]]

Drag options to blanks, or click blank then click option'

A+

B-

C*

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operators in the loop.

Returning dp at wrong index.

The bottom-up approach sums the two previous Fibonacci numbers and returns dp[n].

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that caches Fibonacci values with memoization.

DSA Python

cache = {0: 0, 1: 1}
fib = lambda n: cache[n] if n in cache else cache.setdefault([1], fib([2]) [3] fib(n-2))

Drag options to blanks, or click blank then click option'

An

Bn-1

C+

Dn+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong keys for cache.

Using wrong operators causing incorrect sums.

The lambda checks cache for n, else sets cache[n] to fib(n-1) + fib(n-2).

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