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

Concept Flow - Recursion Concept and Call Stack Visualization

Function Called

↓

Check Base Case?

Yes→Return Base Value

No↓

Call Function Again (Recursive Call)

↓

Wait for Recursive Result

↓

Process Result

↓

Return Result

↩Back to Caller or End

Shows how a recursive function calls itself until a base case is met, then returns results back up the call stack.

Execution Sample

DSA C

int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}

int main() {
  printf("%d", factorial(3));
  return 0;
}

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

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 if n==0	3	factorial(3)	No	factorial(3)
3	Call factorial(2)	2	factorial(2) -> factorial(3)		factorial(2) ↑ factorial(3)
4	Check if n==0	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 if n==0	1	factorial(1) -> factorial(2) -> factorial(3)	No	factorial(1) ↑ factorial(2) ↑ factorial(3)
7	Call factorial(0)	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)		factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
8	Check if n==0	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	Yes	factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
9	Return 1 (base case)	0	factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)	1	factorial(0) returns 1 ↑ factorial(1) ↑ factorial(2) ↑ factorial(3)
10	Calculate 1 * 1	1	factorial(1) -> factorial(2) -> factorial(3)		factorial(1)
11	Return 1	1	factorial(1) -> factorial(2) -> factorial(3)	1	factorial(1) returns 1 ↑ factorial(2) ↑ factorial(3)
12	Calculate 2 * 1	2	factorial(2) -> factorial(3)		factorial(2)
13	Return 2	2	factorial(2) -> factorial(3)	2	factorial(2) returns 2 ↑ factorial(3)
14	Calculate 3 * 2	3	factorial(3)		factorial(3)
15	Return 6	3	factorial(3)	6	factorial(3) returns 6
16	Print result			6

💡 Recursion ends when base case n==0 is reached and returns 1; then results return back up the call stack.

Variable Tracker

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

Key Moments - 3 Insights

Why does the function keep calling itself instead of stopping immediately?

Because the base case (n == 0) is not met yet, so the function calls itself with n-1 as shown in steps 2, 4, 6, and 8 in the execution table.

How does the function know when to stop calling itself?

When n equals 0, the base case is true (step 8), so it returns 1 instead of calling itself again, stopping further recursion.

Why do we see multiple calls stacked before any return happens?

Each recursive call waits for the result of the next call before it can compute its own return value, creating a stack of calls as shown in the 'Call Stack' column until the base case returns.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the current call stack?

A factorial(3)

B factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

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

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

💡 Hint

Check the 'Call Stack (Top to Bottom)' column at step 7 in the execution table.

At which step does the base case condition become true?

A Step 6

B Step 8

C Step 10

D Step 12

💡 Hint

Look for 'Check if n==0' with 'Yes' in the 'Return Value' column in the execution table.

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

A It would be 5 instead of 4

B It would remain 4

C It would be 3 instead of 4

D It would be 1

💡 Hint

The call stack depth increases by one for each recursive call; check 'Call Stack Depth' in variable_tracker.

Concept Snapshot

Recursion calls a function inside itself until a base case stops it.
Each call waits for the next call's result, building a call stack.
Base case returns a value without recursion.
Results return back up the stack, combining to final answer.
Visualize recursion as stacking calls then unstacking returns.

Full Transcript

Recursion is when a function calls itself to solve smaller parts of a problem. It keeps calling itself until it reaches a base case, which stops the recursion. Each call waits for the next call to finish, creating a stack of calls known as the call stack. When the base case returns a value, each previous call uses that value to compute its own result and returns it back up. This process continues until the first call returns the final answer. The example code calculates factorial by multiplying n by factorial of n-1 until n is zero. The execution table shows each call, the current value of n, the call stack, and return values step by step. The variable tracker shows how n, return values, and call stack depth change over time. Key moments clarify why recursion continues until the base case and why calls stack up before returning. The visual quiz tests understanding of call stack state and base case timing. Recursion is like stacking plates: you keep stacking until you reach the bottom plate, then you unstack them one by one to get the final result.