Recursion Concept and Call Stack Visualization in DSA Typescript - Execution Trace

Concept Flow - Recursion Concept and Call Stack Visualization

Call function with input n

↓

Check base case: n <= 1?

Yes→Return base value

No↓

Call function recursively with n-1

↓

Wait for recursive call result

↓

Process result and return

↓

Function call ends, return to previous call

Shows how a recursive function calls itself, waits for the smaller problem to solve, then processes and returns the result, unwinding the call stack.

Execution Sample

DSA Typescript

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

Calculates factorial of 3 using recursion, multiplying n by factorial of n-1 until base case.

Execution Table

Step	Operation	Current n	Call Stack (Top to Bottom)	Return Value	Visual Call Stack
1	Call factorial(3)	3	factorial(3)		factorial(3)
2	Check base case n<=1	3	factorial(3)	No	factorial(3)
3	Call factorial(2)	2	factorial(2) -> factorial(3)		factorial(2) ↑ factorial(3)
4	Check base case n<=1	2	factorial(2) -> factorial(3)	No	factorial(2) ↑ factorial(3)
5	Call factorial(1)	1	factorial(1) -> factorial(2) -> factorial(3)		factorial(1) ↑ factorial(2) ↑ factorial(3)
6	Check base case n<=1	1	factorial(1) -> factorial(2) -> factorial(3)	Yes	factorial(1) ↑ factorial(2) ↑ factorial(3)
7	Return 1 from factorial(1)	1	factorial(1) -> factorial(2) -> factorial(3)	1	factorial(1) returns 1 ↑ factorial(2) ↑ factorial(3)
8	Calculate 2 * 1 in factorial(2)	2	factorial(2) -> factorial(3)		factorial(2)
9	Return 2 from factorial(2)	2	factorial(2) -> factorial(3)	2	factorial(2) returns 2 ↑ factorial(3)
10	Calculate 3 * 2 in factorial(3)	3	factorial(3)		factorial(3)
11	Return 6 from factorial(3)	3	factorial(3)	6	factorial(3) returns 6
12	End of recursion, call stack empty

💡 Recursion ends when base case n <= 1 is reached and all calls return their results.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
n	-	3	2	1	2	3	-	-
Return Value	-				1	2	6	6
Call Stack Depth	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why does the function keep calling itself before returning any value?

Because each call waits for the smaller problem (n-1) to solve first, as shown in steps 3, 5, and 7 in the execution_table where calls stack up before returning.

What is the base case and why is it important?

The base case is when n <= 1 (step 6), which stops further recursive calls and starts returning values back up the call stack, preventing infinite recursion.

How does the call stack visually grow and shrink during recursion?

The call stack grows as new calls are made (steps 1, 3, 5) and shrinks as calls return values (steps 7, 9, 11), shown clearly in the Visual Call Stack column.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the call stack state?

A factorial(3)

B factorial(2) -> factorial(3)

C factorial(1) -> factorial(2) -> factorial(3)

D Empty

💡 Hint

Check the 'Call Stack (Top to Bottom)' column at step 5 in the execution_table.

At which step does the base case condition become true?

A Step 6

B Step 4

C Step 8

D Step 10

💡 Hint

Look at the 'Check base case n<=1' operation and 'Return Value' columns in the execution_table.

If we change the input to factorial(4), how would the call stack depth change at step 5?

A It would be 3

B It would be 4

C It would be 2

D It would be 1

💡 Hint

Refer to the 'Call Stack Depth' row in variable_tracker and understand how input n affects recursion depth.

Concept Snapshot

Recursion calls a function within itself to solve smaller problems.
Each call waits for the next until base case is reached.
Base case stops recursion and starts returning values.
Call stack grows with each call and shrinks as calls return.
Visualizing call stack helps understand recursion flow.

Full Transcript

Recursion is a method where a function calls itself to solve smaller parts of a problem. The process continues until a base case is met, which stops further calls. Each recursive call waits for the next call to finish before it can return its result. This creates a call stack that grows as calls are made and shrinks as results return. Visualizing this call stack helps beginners understand how recursion works step-by-step. In the example of factorial(3), the function calls factorial(2), then factorial(1), reaches the base case, and then returns values back up the stack multiplying as it goes.

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