Recursion Base Case and Recursive Case in DSA C - Execution Trace

Concept Flow - Recursion Base Case and Recursive Case

Start Recursive Function

↓

Check Base Case?

Yes→Return Base Value

No↓

Perform Recursive Call with Smaller Input

↓

Combine Result and Return

↓

End

The function checks if it reached the simplest case (base case). If yes, it returns a value. Otherwise, it calls itself with a smaller input and combines the result.

Execution Sample

DSA C

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

Calculates factorial of n using recursion with a base case when n is 0.

Execution Table

Step	Call Stack	Current n	Condition (n==0?)	Action	Return Value	Visual Call Stack
1	factorial(3)	3	No	Call factorial(2)		factorial(3)
2	factorial(3) -> factorial(2)	2	No	Call factorial(1)		factorial(3) └─ factorial(2)
3	factorial(3) -> factorial(2) -> factorial(1)	1	No	Call factorial(0)		factorial(3) └─ factorial(2) └─ factorial(1)
4	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	0	Yes	Return 1	1	factorial(3) └─ factorial(2) └─ factorial(1) └─ factorial(0)
5	factorial(3) -> factorial(2) -> factorial(1)	1	-	Return 1 * 1 = 1	1	factorial(3) └─ factorial(2) └─ factorial(1)
6	factorial(3) -> factorial(2)	2	-	Return 2 * 1 = 2	2	factorial(3) └─ factorial(2)
7	factorial(3)	3	-	Return 3 * 2 = 6	6	factorial(3)
8	-	-	-	All calls returned, final result = 6	6	-

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

Variable Tracker

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

Key Moments - 3 Insights

Why does the recursion stop at n == 0 and not before?

Because the base case condition (n == 0) is checked at each call (see Step 4 in execution_table). When true, it returns a value without further calls, stopping recursion.

What happens to the call stack when a recursive call returns?

The call stack shrinks as each function returns its result (see Steps 5 to 7). Each return removes the top call, moving back to the previous call.

Why do we multiply n by factorial(n-1) after the recursive call?

Because factorial(n) = n * factorial(n-1). The multiplication happens after the recursive call returns its value (see Step 5 and onwards).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the return value when n == 0?

A n

B 0

C 1

D Undefined

💡 Hint

Check the 'Return Value' column at Step 4 in execution_table.

At which step does the call stack start to shrink?

A Step 3

B Step 5

C Step 4

D Step 7

💡 Hint

Look at the 'Call Stack' and 'Visual Call Stack' columns from Step 4 to Step 5.

If the base case was changed to n == 1, how would the execution_table change?

A Recursion would stop one step earlier, base case reached at n==1

B Recursion would stop earlier, base case reached at n==0

C No change in recursion steps

D Recursion would never stop

💡 Hint

Think about when the base case condition is true and when recursion stops.

Concept Snapshot

Recursion has two parts:
- Base Case: stops recursion (e.g., if n==0 return 1)
- Recursive Case: calls itself with smaller input (e.g., n * factorial(n-1))
Each call waits for the next call to return before finishing.
Without base case, recursion never ends and causes error.

Full Transcript

Recursion works by a function calling itself with smaller inputs until it reaches a base case. The base case stops further calls and returns a simple value. Then each previous call uses that returned value to compute its own result and return it. For example, factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0). At factorial(0), the base case returns 1. Then factorial(1) returns 1*1=1, factorial(2) returns 2*1=2, and factorial(3) returns 3*2=6. The call stack grows with each call and shrinks as calls return. This process ensures the problem is solved step-by-step.