Why Dynamic Programming and When Recursion Alone Fails in DSA Go - 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 classic problem where recursion alone can be slow because it repeats the same calculations many times. Dynamic Programming helps us solve this efficiently by remembering past results.

🎯 Goal: You will build a Go program that first uses simple recursion to count ways to climb stairs, then add a memory helper to avoid repeated work, showing why dynamic programming is better.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Add a map to remember results for each step count

Modify the recursive function to use the map for faster results

Print the number of ways to climb 5 steps using both methods

💡 Why This Matters

🌍 Real World

Counting ways to climb stairs models many problems like counting paths, sequences, or combinations where overlapping subproblems occur.

💼 Career

Understanding dynamic programming is essential for software engineers to write efficient algorithms and solve complex problems in interviews and real projects.

1

Create a recursive function to count ways to climb stairs

Write a recursive function called countWays that takes an integer n representing steps left and returns the number of ways to climb those steps. Use the rule: if n is 0 or 1, return 1; otherwise, return countWays(n-1) + countWays(n-2). Then call countWays(5) and store the result in a variable called waysRecursive.

DSA Go

package main

import "fmt"

func countWays(n int) int {
    // Your code here
}

func main() {
    // Call countWays(5) and store in waysRecursive
    // Your code here
}

Hint

Think of the base cases when steps left are 0 or 1. For other cases, add results of smaller problems.

2

Add a map to remember results for each step count

Create a map called memo of type map[int]int to store previously calculated results for each number of steps. Initialize it as an empty map in main.

DSA Go

package main

import "fmt"

func countWays(n int) int {
    if n == 0 || n == 1 {
        return 1
    }
    return countWays(n-1) + countWays(n-2)
}

func main() {
    // Create memo map here
    // Your code here
    waysRecursive := countWays(5)
    _ = waysRecursive
}

Hint

Use make(map[int]int) to create an empty map for memoization.

3

Modify the recursive function to use the map for faster results

Change the countWays function to take a second parameter memo map[int]int. Before computing, check if n is in memo. If yes, return the stored value. Otherwise, compute the result recursively, store it in memo[n], and return it. Update the call in main to pass memo.

DSA Go

package main

import "fmt"

func countWays(n int, memo map[int]int) int {
    // Your code here
}

func main() {
    memo := make(map[int]int)
    // Call countWays with memo
    // Your code here
}

Hint

Use the map to check if the answer is already known before computing.

4

Print the number of ways to climb 5 steps using both methods

In main, call the original recursive function countWaysSimple (which you will create as a copy of the original countWays without memo) with 5 steps and store in waysSimple. Then call the memoized countWays with 5 steps and memo and store in waysMemo. Finally, print both results with labels "Ways with simple recursion:" and "Ways with memoization:".

DSA Go

package main

import "fmt"

func countWaysSimple(n int) int {
    // Your code here
}

func countWays(n int, memo map[int]int) int {
    if n == 0 || n == 1 {
        return 1
    }
    if val, found := memo[n]; found {
        return val
    }
    memo[n] = countWays(n-1, memo) + countWays(n-2, memo)
    return memo[n]
}

func main() {
    memo := make(map[int]int)
    // Call countWaysSimple(5) and store in waysSimple
    // Call countWays(5, memo) and store in waysMemo
    // Print both results
    // Your code here
}

Hint

Print the results using fmt.Println with clear labels.

Practice

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

easy

A. Because dynamic programming uses less memory than recursion

B. Because dynamic programming stores results to avoid repeated work

C. Because recursion cannot solve problems with multiple choices

D. Because recursion is always slower than loops

Solution

1. Step 1: Understand recursion's limitation

   Recursion often recalculates the same subproblems multiple times, causing inefficiency.

2. Step 2: Role of dynamic programming

   Dynamic programming saves results of subproblems (memoization) to avoid repeated calculations.

3. Final Answer:

   Because dynamic programming stores results to avoid repeated work -> Option B

4. Quick Check:

   Memoization avoids repeated work = D [OK]

Hint: Dynamic programming saves repeated results to speed up recursion [OK]

Common Mistakes:

• Thinking recursion is always slower than loops
• Believing recursion can't handle multiple choices
• Confusing memory use between recursion and DP

2. Which Go syntax correctly declares a recursive function to compute Fibonacci numbers?

easy

A. func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) }

B. func fib(n int) { if n <= 1 { return n } return fib(n-1) + fib(n-2) }

C. func fib(n int) int { if n < 0 { return 0 } return fib(n-1) + fib(n-2) }

D. func fib(n int) int { if n == 0 { return 0 } else { return fib(n-1) + fib(n-2) } }

Solution

1. Step 1: Check function signature and return type

   func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) } correctly declares return type int and returns int values.

2. Step 2: Verify base cases and recursion

   func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) } uses base case n <= 1 returning n, and recursive calls fib(n-1)+fib(n-2), which is correct.

3. Final Answer:

   func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) } -> Option A

4. Quick Check:

   Correct signature and base case = B [OK]

Hint: Check function return type and base cases carefully [OK]

Common Mistakes:

• Missing return type in function signature
• Incorrect base case conditions
• Returning void instead of int

3. What is the output of this Go code snippet?

import "fmt"

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    fmt.Println(fib(5))
}

medium

A. 13

B. 8

C. 5

D. Error

Solution

1. Step 1: Trace fib(5) calls

   fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), etc.

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Off-by-one errors in base cases
• Assuming output is sum of first 5 numbers

4. Identify the bug in this recursive Fibonacci function and choose the fix:

func fib(n int) int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    }
    return fib(n-1) + fib(n-3)
}

medium

A. Change return type to float64

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

C. Add memoization to store results

D. Change fib(n-3) to fib(n-2) in the return statement

Solution

1. Step 1: Analyze recursive calls

   Function calls fib(n-1) + fib(n-3), but Fibonacci requires fib(n-1) + fib(n-2).

2. Step 2: Correct the recursive call

   Changing fib(n-3) to fib(n-2) fixes the logic to standard Fibonacci recursion.

3. Final Answer:

   Change fib(n-3) to fib(n-2) in the return statement -> Option D

4. Quick Check:

   Correct recursion calls = A [OK]

Hint: Fibonacci sums fib(n-1) and fib(n-2) only [OK]

Common Mistakes:

• Using wrong recursive indices
• Ignoring base cases
• Adding memoization without fixing recursion

5. You want to compute the nth Fibonacci number efficiently in Go. Which approach best avoids the exponential time of plain recursion?

hard

A. Use dynamic programming with memoization to store intermediate results

B. Use a tail-recursive version of Fibonacci

C. Use recursion with a global variable to count calls

D. Use recursion with multiple goroutines to parallelize calls

Solution

1. Step 1: Understand recursion inefficiency

   Plain recursion recalculates subproblems exponentially many times, causing slow performance.

2. Step 2: Compare approaches to optimize

   Memoization stores results to avoid repeated work, reducing time to linear - classic DP approach.

3. Step 3: Evaluate other options

   Global variable counting calls doesn't improve speed. Parallel recursion adds overhead and complexity without guaranteed speedup.

4. Final Answer:

   Use dynamic programming with memoization to store intermediate results -> Option A

5. Quick Check:

   Memoization avoids repeated work = C [OK]

Hint: Memoize results to avoid repeated recursion calls [OK]

Common Mistakes:

• Thinking parallel recursion always speeds up
• Using global counters instead of caching
• Thinking tail recursion avoids exponential time