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.