Why Dynamic Programming and When Recursion Alone Fails in DSA Python - See It Work

Why Dynamic Programming and When Recursion Alone Fails

📖 Scenario: Imagine you want to find the number of ways to climb a staircase with 5 steps. You can take either 1 step or 2 steps at a time. This is a common problem where recursion alone can be slow because it repeats the same calculations many times.We will explore how recursion works here and why it can be inefficient. Then, we will prepare to use dynamic programming to solve it faster.

🎯 Goal: Build a simple recursive function to count ways to climb stairs and see why it repeats work. Then, prepare a structure to store results to avoid repeated work.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Use a dictionary to store intermediate results (memoization)

Show how recursion repeats calculations without memoization

Prepare for dynamic programming by adding a cache dictionary

💡 Why This Matters

🌍 Real World

Counting ways to climb stairs is like many real problems where choices build on smaller subproblems, such as route planning or resource allocation.

💼 Career

Understanding when recursion is inefficient and how dynamic programming improves it is key for software engineers solving optimization problems.

1

Create a recursive function to count ways to climb stairs

Create a function called count_ways that takes an integer n and returns the number of ways to climb n stairs by taking 1 or 2 steps at a time. Use simple recursion with these rules:
- If n is 0 or 1, return 1
- Otherwise, return count_ways(n - 1) + count_ways(n - 2)

DSA Python

# Define the recursive function count_ways(n)
# Your code here

Hint

Think about the base cases first: when there are 0 or 1 steps, there is only 1 way to climb.

For other cases, the ways to climb are the sum of ways to climb the previous step and the step before that.

2

Call the recursive function for 5 stairs

Create a variable called stairs and set it to 5. Then create a variable called result and set it to the result of calling count_ways(stairs).

DSA Python

def count_ways(n):
    if n == 0 or n == 1:
        return 1
    return count_ways(n - 1) + count_ways(n - 2)

# Create variable stairs and set to 5
# Create variable result and call count_ways(stairs)
# Your code here

Hint

Set stairs to 5 because we want to find ways to climb 5 steps.

Call the function with stairs and save the answer in result.

3

Add a dictionary to store intermediate results (memoization)

Create a dictionary called memo outside the function and pass it as a parameter to count_ways with default value {}. Inside the function, check if n is in memo. If yes, return memo[n]. Otherwise, compute the result recursively, store it in memo[n], and return it.

DSA Python

memo = {}
def count_ways(n, memo={}):
    # Check if n is in memo
    # If yes, return memo[n]
    # If no, compute result recursively and store in memo[n]
    # Your code here

stairs = 5
result = count_ways(stairs, memo)

Hint

Use the dictionary memo to remember answers for each n.

This way, the function does not repeat work for the same n.

4

Print the result to see the number of ways to climb 5 stairs

Write a print statement to display the value of result.

DSA Python

memo = {}
def count_ways(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        return 1
    memo[n] = count_ways(n - 1, memo) + count_ways(n - 2, memo)
    return memo[n]

stairs = 5
result = count_ways(stairs, memo)

# Print the result
# Your code here

Hint

Use print(result) to show the number of ways to climb 5 stairs.

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