Why Recursion Concept and Call Stack Visualization in DSA Typescript?

The Big Idea

Discover how a function can cleverly call itself to solve big problems step-by-step!

The Scenario

Imagine you need to find the factorial of a number by multiplying all numbers from 1 up to that number. Doing this by writing repeated multiplication steps manually for each number is tiring and error-prone.

The Problem

Manually multiplying each number one by one takes a lot of time and effort, especially for big numbers. It's easy to make mistakes or forget a step, and the code becomes long and hard to read.

The Solution

Recursion lets a function call itself to solve smaller parts of the problem until it reaches the simplest case. This way, the code stays short and clear, and the computer handles the repeated steps automatically using a call stack.

Before vs After

✗ Before

function factorial(n: number): number {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

✓ After

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

What It Enables

Recursion enables solving complex problems by breaking them into simpler, repeatable steps handled automatically by the call stack.

Real Life Example

Think of Russian nesting dolls: to open the biggest doll, you first open the smaller one inside it, and so on, until you reach the smallest doll. Recursion works similarly by solving smaller parts first.

Key Takeaways

Manual repetition is slow and error-prone.

Recursion breaks problems into smaller, manageable parts.

The call stack keeps track of each step automatically.

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