Recursion Concept and Call Stack Visualization in DSA Typescript - Build from Scratch

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you are stacking boxes one on top of another. To find out how many boxes are stacked, you can count one box and then ask the smaller stack below to count itself. This is like recursion, where a problem is solved by solving smaller versions of the same problem.

🎯 Goal: You will build a simple recursive function in TypeScript that counts down from a given number to 1, printing each step. This will help you see how recursion works and how the call stack grows and shrinks.

📋 What You'll Learn

Create a variable called startNumber with the value 5

Create a recursive function called countDown that takes a number parameter n

Inside countDown, print the current number n

Make countDown call itself with n - 1 if n is greater than 1

Call countDown with startNumber

Print each number on its own line

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching files in folders, solving puzzles, and processing nested data.

💼 Career

Understanding recursion helps in software development roles that involve algorithms, data processing, and problem solving.

1

Create the starting number

Create a variable called startNumber and set it to 5.

DSA Typescript

# Your code here

Hint

Use const startNumber = 5; to create the variable.

2

Define the recursive function

Create a function called countDown that takes a parameter n of type number.

DSA Typescript

const startNumber = 5;

// Define the recursive function countDown here
# Your code here

Hint

Write function countDown(n: number): void { } to define the function.

3

Add the recursive logic

Inside countDown, print the current number n using console.log(n). Then, if n is greater than 1, call countDown again with n - 1.

DSA Typescript

const startNumber = 5;

function countDown(n: number): void {
    // Print n
    // If n > 1, call countDown with n - 1
    # Your code here
}

Hint

Use console.log(n); to print and if (n > 1) { countDown(n - 1); } for recursion.

4

Call the function and see the output

Call the function countDown with the variable startNumber to start the countdown and print the numbers.

DSA Typescript

const startNumber = 5;

function countDown(n: number): void {
    console.log(n);
    if (n > 1) {
        countDown(n - 1);
    }
}

// Call countDown with startNumber
# Your code here

Hint

Write countDown(startNumber); to start the countdown.

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