Why Dynamic Programming and When Recursion Alone Fails in DSA Javascript - 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 climb 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.

🎯 Goal: You will build a simple program to count the ways to climb the stairs using recursion first, then add a helper to remember past results (dynamic programming) to make it faster.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Add a cache object to store results of previous calculations

Modify the recursive function to use the cache to avoid repeated work

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Counting ways to climb stairs is like many real problems where you combine smaller solutions to build bigger answers, such as planning routes or making change with coins.

💼 Career

Understanding when recursion is slow and how dynamic programming speeds it up is key for software engineers solving optimization and combinatorial problems.

1

Create a recursive function to count ways to climb stairs

Write a function called countWays that takes a number n and returns the number of ways to climb n steps. Use recursion with these rules: if n is 0 or 1, return 1; otherwise, return countWays(n - 1) + countWays(n - 2).

DSA Javascript

// Your code here
// Write function countWays(n) using recursion

Hint

Think of the base cases first: when there are 0 or 1 steps, there is only 1 way to climb. For other cases, add the ways to climb n-1 and n-2 steps.

2

Add a cache object to store previous results

Create an empty object called cache outside the function countWays to store results of previous calculations.

DSA Javascript

function countWays(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return countWays(n - 1) + countWays(n - 2);
}

// Create cache object here
// Your code here

Hint

This object will help us remember answers for each n so we don't calculate them again.

3

Modify the recursive function to use the cache

Update the function countWays to first check if n is in cache. If yes, return the cached value. Otherwise, calculate the value recursively, store it in cache[n], and then return it.

DSA Javascript

const cache = {};

function countWays(n) {
    // Check cache here
    // Your code here

    if (n === 0 || n === 1) {
        return 1;
    }

    // Calculate and store in cache
    // Your code here
}

Hint

Use if (n in cache) to check if the answer is already saved. Save new answers with cache[n] = ....

4

Print the number of ways to climb 5 steps

Write a console.log statement to print the result of countWays(5).

DSA Javascript

const cache = {};

function countWays(n) {
    if (n in cache) {
        return cache[n];
    }
    if (n === 0 || n === 1) {
        return 1;
    }
    cache[n] = countWays(n - 1) + countWays(n - 2);
    return cache[n];
}

// Print the number of ways to climb 5 steps
// Your code here

Hint

Use console.log(countWays(5)) to see the total ways to climb 5 steps.

Practice

1. Why does recursion alone sometimes fail or become inefficient for certain problems like Fibonacci sequence calculation?

easy

A. Because recursion can repeat the same calculations many times, causing slow performance

B. Because recursion always uses loops which are slow

C. Because recursion cannot handle base cases

D. Because recursion does not use any memory

Solution

1. Step 1: Understand recursion behavior in repeated calculations

   Recursion calls itself with smaller inputs but may recompute the same values multiple times, like Fibonacci(5) calling Fibonacci(4) and Fibonacci(3), and Fibonacci(4) again calling Fibonacci(3).

2. Step 2: Identify inefficiency due to repeated work

   This repeated work causes exponential time complexity, making recursion alone slow for large inputs.

3. Final Answer:

   Because recursion can repeat the same calculations many times, causing slow performance -> Option A

4. Quick Check:

   Repeated calculations cause inefficiency = C [OK]

Hint: Look for repeated calls with same inputs causing slow recursion [OK]

Common Mistakes:

• Thinking recursion always uses loops
• Believing recursion can't handle base cases
• Assuming recursion never uses memory

2. Which of the following is the correct syntax to implement memoization in a recursive JavaScript function?

easy

A. Use a cache object to store results and check before recursive calls

B. Use a for loop inside the recursive function

C. Call the recursive function without any parameters

D. Return undefined for base cases

Solution

1. Step 1: Understand memoization concept

   Memoization stores results of expensive function calls in a cache object to avoid repeated calculations.

2. Step 2: Apply memoization in recursion

   Before making a recursive call, check if the result exists in cache; if yes, return it; else compute and store it.

3. Final Answer:

   Use a cache object to store results and check before recursive calls -> Option A

4. Quick Check:

   Memoization uses cache to avoid repeats = A [OK]

Hint: Use a cache object to save and reuse results [OK]

Common Mistakes:

• Using loops inside recursion unnecessarily
• Not passing parameters to recursive calls
• Returning undefined for base cases

3. What will be the output of the following JavaScript code snippet?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. Undefined

B. 8

C. 5

D. 3

Solution

1. Step 1: Trace fib(5) with memoization

   fib(5) calls fib(4) and fib(3), storing results in memo. fib(4) = 3, fib(3) = 2, so fib(5) = 3 + 2 = 5.

2. Step 2: Confirm memo usage avoids repeated calls

   Memo stores intermediate results, so no repeated calculations, final output is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 with memoization [OK]

Hint: Memoization returns correct Fibonacci quickly [OK]

Common Mistakes:

• Confusing Fibonacci(5) with Fibonacci(6)
• Ignoring memo cache effect
• Assuming output is sum of all calls

4. Identify the error in this recursive function for factorial and fix it:

function factorial(n) {
  if (n === 0) return 0;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. Recursive call should be factorial(n + 1)

B. No error, output is correct

C. Function should return n + factorial(n - 1)

D. Base case should return 1 instead of 0

Solution

1. Step 1: Check base case correctness

   Factorial of 0 is 1, but function returns 0, causing all results to be zero.

2. Step 2: Fix base case return value

   Change base case to return 1 so multiplication works correctly.

3. Final Answer:

   Base case should return 1 instead of 0 -> Option D

4. Quick Check:

   Factorial base case = 1 [OK]

Hint: Factorial(0) must return 1, not 0 [OK]

Common Mistakes:

• Returning 0 for base case
• Using wrong recursive call direction
• Adding instead of multiplying

5. You want to find the minimum number of coins needed to make a certain amount using coin denominations [1, 3, 4]. Why is dynamic programming better than plain recursion here, and how would you apply it?

hard

A. Dynamic programming uses loops only; recursion cannot solve coin problems

B. Dynamic programming stores results of subproblems to avoid repeated work; apply bottom-up or memoized recursion

C. Recursion is faster because it tries all combinations without storing results

D. Dynamic programming ignores smaller amounts and solves only the final amount

Solution

1. Step 1: Understand problem complexity with recursion

   Recursion tries all combinations repeatedly, causing exponential time and slow performance.

2. Step 2: Use dynamic programming to store subproblem results

   DP saves minimum coins needed for smaller amounts, reusing them to build solution for larger amounts efficiently.

3. Step 3: Apply bottom-up or memoized recursion approach

   Either build from smallest amount up or use recursion with memo cache to avoid repeated calculations.

4. Final Answer:

   Dynamic programming stores results of subproblems to avoid repeated work; apply bottom-up or memoized recursion -> Option B

5. Quick Check:

   DP avoids repeats with caching = A [OK]

Hint: Store subproblem results to avoid repeated calculations [OK]

Common Mistakes:

• Thinking recursion alone is faster
• Believing DP ignores smaller problems
• Confusing loops with DP necessity