Recursion Concept and Call Stack Visualization in DSA Javascript

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

Analogy: Imagine a set of nested Russian dolls where you open one doll to find a smaller one inside, and you keep opening until you find the smallest doll that doesn't open. Then you close them back in reverse order.

function call stack:
main -> func(3) ↑
          func(2)
          func(1)
          base case reached
          returning back up

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down into smaller factorial calls

Step 1: Call factorial(3), which calls factorial(2)

call stack: main -> factorial(3) ↑

Why: We start with the problem 3! and break it down to factorial(2)

Step 2: Call factorial(2), which calls factorial(1)

call stack: main -> factorial(3) -> factorial(2) ↑

Why: We continue breaking down the problem to smaller parts

Step 3: Call factorial(1), which calls factorial(0)

call stack: main -> factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Keep breaking down until the base case

Step 4: Call factorial(0), base case reached, return 1

call stack: main -> factorial(3) -> factorial(2) -> factorial(1) -> factorial(0) ↑

Why: Base case stops recursion and starts returning values

Step 5: Return from factorial(0) to factorial(1): 1 x 1 = 1

call stack: main -> factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Calculate factorial(1) using returned value

Step 6: Return from factorial(1) to factorial(2): 2 x 1 = 2

call stack: main -> factorial(3) -> factorial(2) ↑

Why: Calculate factorial(2) using returned value

Step 7: Return from factorial(2) to factorial(3): 3 x 2 = 6

call stack: main -> factorial(3) ↑

Why: Calculate factorial(3) using returned value

Step 8: Return final result 6 to main

call stack: main ↑

Why: Recursion complete, final answer returned

Result:

final result: 6

Annotated Code

DSA Javascript

class Factorial {
  static factorial(n) {
    if (n === 0) {
      return 1; // base case: factorial(0) = 1
    }
    return n * Factorial.factorial(n - 1); // recursive call
  }
}

// Driver code
const input = 3;
const result = Factorial.factorial(input);
console.log(`Factorial of ${input} is ${result}`);

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

base case stops recursion when n reaches 0

return n * Factorial.factorial(n - 1);

recursive call reduces problem size by 1 each time

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until it reaches the base case

Space: O(n) because each recursive call adds a new layer to the call stack

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for problems like factorial

Edge Cases

n = 0 (base case)

Returns 1 immediately without further recursion

DSA Javascript

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

n = 1

Calls factorial(0) then returns 1 x 1 = 1

DSA Javascript

return n * Factorial.factorial(n - 1);

negative n (not handled)

Function will recurse infinitely causing stack overflow

DSA Javascript

No guard for negative input in code

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a clear stopping point, use recursion to simplify the solution.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call moves closer to the base case

Summary

Recursion solves problems by calling the same function with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The key insight is the base case stops recursion and the call stack remembers each step to combine results.

Practice

1. What happens when a recursive function calls itself without a base case?

easy

A. It returns immediately without doing anything

B. It causes an infinite loop leading to a stack overflow error

C. It executes only once and stops

D. It throws a syntax error

Solution

1. Step 1: Understand the role of base case in recursion

   The base case stops the recursion by providing a condition to end calls.

2. Step 2: Analyze what happens without a base case

   Without a base case, the function keeps calling itself endlessly, filling the call stack.

3. Final Answer:

   It causes an infinite loop leading to a stack overflow error -> Option B

4. Quick Check:

   No base case = infinite recursion = stack overflow [OK]

Hint: Always check for a base case to stop recursion [OK]

Common Mistakes:

• Thinking recursion stops automatically
• Confusing base case with recursive case
• Assuming syntax error occurs without base case

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

easy

A. function countDown(n) { if(n <= 0) return; countDown(n - 1); }

B. function countDown(n) { while(n > 0) countDown(n - 1); }

C. function countDown(n) { for(let i=0; i

D. function countDown(n) { if(n < 0) countDown(n + 1); }

Solution

1. Step 1: Identify correct base case and recursive call

   function countDown(n) { if(n <= 0) return; countDown(n - 1); } has a base case (if n <= 0 return) and calls itself with n-1.

2. Step 2: Check other options for syntax or logic errors

   function countDown(n) { while(n > 0) countDown(n - 1); } uses while loop causing infinite recursion; C uses for loop incorrectly; D lacks proper base case.

3. Final Answer:

   function countDown(n) { if(n <= 0) return; countDown(n - 1); } -> Option A

4. Quick Check:

   Base case + recursive call = correct syntax [OK]

Hint: Look for base case and self-call in function [OK]

Common Mistakes:

• Using loops instead of recursion
• Missing base case
• Wrong recursive call argument

3. What is the output of the following code?

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

medium

A. 9

B. 1

C. 3

D. 6

Solution

1. Step 1: Trace factorial calls for n=3

   factorial(3) = 3 * factorial(2); factorial(2) = 2 * factorial(1); factorial(1) = 1 * factorial(0); factorial(0) = 1.

2. Step 2: Calculate return values step-by-step

   factorial(1) = 1 * 1 = 1; factorial(2) = 2 * 1 = 2; factorial(3) = 3 * 2 = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   3! = 6 [OK]

Hint: Factorial n! = n * (n-1)! [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting base case returns 1
• Calculating factorial(0) incorrectly

4. Find the error in this recursive function that calculates the sum of numbers from 1 to n:

function sum(n) {
  if (n === 1) return 1;
  return n + sum(n);
}

medium

A. The base case is missing

B. The function should return n - sum(n - 1)

C. The recursive call uses the same argument causing infinite recursion

D. The function should use a loop instead

Solution

1. Step 1: Check the recursive call argument

   The function calls sum(n) again without reducing n, causing infinite recursion.

2. Step 2: Identify correct recursive call

   It should call sum(n - 1) to reduce n and reach base case.

3. Final Answer:

   The recursive call uses the same argument causing infinite recursion -> Option C

4. Quick Check:

   Recursive call argument must change to reach base case [OK]

Hint: Recursive call argument must move toward base case [OK]

Common Mistakes:

• Calling function with same argument
• Missing base case
• Using wrong operator in return

5. Consider this recursive function that reverses a string:

function reverseStr(str) {
  if (str === "") return "";
  return reverseStr(str.substring(1)) + str[0];
}
console.log(reverseStr("code"));

What is the output and why?

hard

A. "edoc" because the function moves first character to the end recursively

B. "code" because substring does not change the string

C. "" because base case returns empty string immediately

D. SyntaxError because substring is used incorrectly

Solution

1. Step 1: Understand recursion on string substring

   The function calls itself with the string minus the first character each time.

2. Step 2: Trace the concatenation on return

   Each call adds the first character of the current string to the end of the reversed substring, reversing the string.

3. Final Answer:

   "edoc" because the function moves first character to the end recursively -> Option A

4. Quick Check:

   Recursive substring + concat reverses string [OK]

Hint: Recursion with substring(1) + first char reverses string [OK]

Common Mistakes:

• Thinking substring does not change string
• Confusing base case effect
• Assuming syntax error with substring