Recursion Concept and Call Stack Visualization in DSA Typescript

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 Russian nesting dolls where each doll contains a smaller doll inside. You open each doll until you find the smallest one, then close them back in reverse order.

function call stack:
main()
  ↓
func() -> func() -> func() -> base case
  ↑       ↑       ↑       ↑
 call1   call2   call3   call4

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Show how recursive calls build up and then resolve using the call stack

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

call stack: factorial(3) ↑
factorial(2) ↑

Why: We break the problem into smaller parts by calling factorial with a smaller number

Step 2: factorial(2) calls factorial(1)

call stack: factorial(3) ↑
factorial(2) ↑
factorial(1) ↑

Why: Keep breaking down until we reach the simplest case

Step 3: factorial(1) calls factorial(0), the base case

call stack: factorial(3) ↑
factorial(2) ↑
factorial(1) ↑
factorial(0) ↑

Why: Base case stops recursion and starts returning values

Step 4: factorial(0) returns 1, factorial(1) returns 1 * 1 = 1

call stack unwinding:
factorial(3) ↑
factorial(2) ↑
factorial(1) returns 1

Why: Start resolving calls by returning results back up the stack

Step 5: factorial(2) returns 2 * 1 = 2

call stack unwinding:
factorial(3) ↑
factorial(2) returns 2

Why: Combine returned values to build the final answer

Step 6: factorial(3) returns 3 * 2 = 6, recursion ends

call stack empty, final result = 6

Why: All calls resolved, final answer is ready

Result:

call stack empty
final result = 6

Annotated Code

DSA Typescript

class Factorial {
  static factorial(n: number): number {
    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; }

Check base case to stop recursion

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

Recursive call with smaller input to build solution

Output

Factorial of 3 is 6

Complexity Analysis

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

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

vs Alternative: Compared to a loop, recursion uses more memory due to call stack but can be simpler to write for problems naturally defined recursively

Edge Cases

Input is 0

Returns 1 immediately as base case

DSA Typescript

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

Input is 1

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

DSA Typescript

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

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a clear stopping point, use recursion to simplify the solution by calling the function within itself.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion, like 'if (n === 0) return 1;'

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call uses a smaller input, e.g., 'factorial(n - 1)'

Summary

Calculates a problem by calling itself with smaller inputs until a simple base case is reached.

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

The key is the base case that stops recursion and the call stack that keeps track of unfinished calls.

Practice

1. What happens when a recursive function calls itself without a stopping condition?

easy

A. It runs only once and stops

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

C. It immediately returns without doing anything

D. It throws a syntax error

Solution

1. Step 1: Understand recursion stopping condition

   A recursive function must have a base case to stop calling itself; otherwise, it keeps calling endlessly.

2. Step 2: Effect of missing stopping condition

   Without a stopping condition, the function calls stack up until memory runs out, causing a stack overflow error.

3. Final Answer:

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

4. Quick Check:

   Missing base case = infinite recursion [OK]

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

Common Mistakes:

• Assuming recursion stops automatically
• Confusing infinite loop with syntax error
• Thinking recursion runs only once without base case

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

easy

A. function recurse(n: number): number { if (n <= 0) return 0; return n + recurse(n - 1); }

B. function recurse(n: number) { while(n > 0) recurse(n - 1); }

C. function recurse(n: number): number { return n + recurse(n + 1); }

D. function recurse(n: number): number { return n * recurse(n); }

Solution

1. Step 1: Check for base case and recursive call

   function recurse(n: number): number { if (n <= 0) return 0; return n + recurse(n - 1); } has a base case (n <= 0) and calls itself with n - 1, which is correct for recursion.

2. Step 2: Analyze other options for errors

   The version with a while loop lacks a proper base case and return statement; another calls recurse with n + 1 causing infinite recursion; another calls recurse with the same n causing infinite recursion.

3. Final Answer:

   function recurse(n: number): number { if (n <= 0) return 0; return n + recurse(n - 1); } -> Option A

4. Quick Check:

   Base case + decreasing argument = correct recursion [OK]

Hint: Look for base case and argument reducing in recursion [OK]

Common Mistakes:

• Missing base case
• Increasing argument causing infinite recursion
• Using loops instead of recursion

3. What is the output of the following TypeScript code?

function factorial(n: number): number {
  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

   factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0) which returns 1.

2. Step 2: Calculate return values

   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 factorial with sum
• Not tracing base case return
• Multiplying incorrectly

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

function sumTo(n: number): number {
  return n + sumTo(n - 1);
}

medium

A. Change n - 1 to n + 1

B. Change return to console.log

C. Add a base case: if (n <= 0) return 0;

D. Remove the recursive call

Solution

1. Step 1: Identify missing base case

   The function lacks a stopping condition, so it will recurse infinitely causing stack overflow.

2. Step 2: Fix by adding base case

   Adding if (n <= 0) return 0; stops recursion when n reaches 0 or less.

3. Final Answer:

   Add a base case: if (n <= 0) return 0; -> Option C

4. Quick Check:

   Base case needed to stop recursion [OK]

Hint: Always add base case to recursive functions [OK]

Common Mistakes:

• Ignoring base case causes infinite recursion
• Changing recursive call incorrectly
• Removing recursion defeats purpose

5. Given the recursive function below, what will be the output when calling printNumbers(3)? Visualize the call stack.

function printNumbers(n: number): void {
  if (n === 0) return;
  printNumbers(n - 1);
  console.log(n);
}

hard

A. 1 2 3

B. 3 2 1

C. 3 3 3

D. 1 1 1

Solution

1. Step 1: Understand call stack order

   printNumbers(3) calls printNumbers(2), which calls printNumbers(1), which calls printNumbers(0) and returns immediately.

2. Step 2: Trace console.log calls after recursion

   After reaching base case, console.log prints 1, then 2, then 3 as the stack unwinds.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Post-recursion print = ascending order [OK]

Hint: Print after recursive call prints ascending order [OK]

Common Mistakes:

• Printing before recursion causes descending order
• Confusing call stack push/pop order
• Expecting repeated numbers