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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci numbers using simple recursion.

DSA Go

func fib(n int) int {
    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 in the recursive return statement.

The Fibonacci sequence is calculated by adding the two previous numbers, so the operator must be '+'.

2fill in blank

medium

Complete the code to add memoization to the Fibonacci function to avoid repeated calculations.

DSA Go

var memo = make(map[int]int)

func fibMemo(n int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fibMemo(n-1) [1] fibMemo(n-2)
    return memo[n]
}

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

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operator or forgetting to store the result in the memo map.

Memoization stores results of fib(n) to avoid recomputation. The addition operator '+' is used to sum the two previous Fibonacci numbers.

3fill in blank

hard

Fix the error in the recursive factorial function to prevent infinite recursion.

DSA Go

func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial([1])
}

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

A0

Bn+1

Cn

Dn-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 or n in recursive call causes infinite recursion.

The factorial function multiplies n by factorial of n-1. Using n-1 moves towards the base case and prevents infinite recursion.

4fill in blank

hard

Fill both blanks to complete the code that uses dynamic programming to find the minimum cost path in a grid.

DSA Go

func minCost(cost [][]int, m int, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    dp[0][0] = cost[0][0]
    for i := 1; i <= m; i++ {
        dp[i][0] = dp[i-1][0] [1] cost[i][0]
    }
    for j := 1; j <= n; j++ {
        dp[0][j] = dp[0][j-1] [2] cost[0][j]
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]
        }
    }
    return dp[m][n]
}

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 causes wrong cost calculation.

To accumulate the cost along the path, we add the current cell cost to the previous minimum cost. So '+' is used in both blanks.

5fill in blank

hard

Fill all three blanks to complete the code that builds a memoized recursive solution for the climbing stairs problem.

DSA Go

var memoClimb = make(map[int]int)

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    if val, ok := memoClimb[[1]]; ok {
        return val
    }
    memoClimb[n] = climbStairs(n-1) [2] climbStairs([3])
    return memoClimb[n]
}

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

An

B+

Cn-2

Dn-3

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong memo key or wrong recursive calls causes incorrect results or infinite recursion.

The memo map stores results for n, so the key is 'n'. The number of ways to climb stairs is sum of ways to climb n-1 and n-2 steps, so '+' and 'n-2' are used.

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