Factorial Using Recursion in DSA C - Execution Trace

Concept Flow - Factorial Using Recursion

Call factorial(n)

↓

Is n == 0 or 1?

Yes→Return 1

No↓

Return n * factorial(n-1)

↓

Recursive call factorial(n-1)

↓

Repeat until base case reached

↓

Unwind calls, multiply results

↓

Final factorial value returned

The function calls itself with n-1 until it reaches 0 or 1, then returns 1 and multiplies back up the call stack.

Execution Sample

DSA C

#include <stdio.h>

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

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

Calculates factorial of 4 by recursive calls multiplying down to 1 and back up.

Execution Table

Step	Call	Argument n	Condition (n==0 or 1?)	Return Value	Stack Depth	Call Stack Visual
1	factorial	4	No	Waiting	1	factorial(4)
2	factorial	3	No	Waiting	2	factorial(4) -> factorial(3)
3	factorial	2	No	Waiting	3	factorial(4) -> factorial(3) -> factorial(2)
4	factorial	1	Yes	1	4	factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)
5	Return from factorial(1)	-	-	1	3	factorial(4) -> factorial(3) -> factorial(2)
6	Return from factorial(2)	-	-	2 * 1 = 2	2	factorial(4) -> factorial(3)
7	Return from factorial(3)	-	-	3 * 2 = 6	1	factorial(4)
8	Return from factorial(4)	-	-	4 * 6 = 24	0	-
9	End	-	-	-	-	-

💡 Recursion ends when base case n == 0 or 1 is reached, then returns multiply back up.

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	4	4	3	2	1	-	-	-	-
Return Value	-	Waiting	Waiting	Waiting	1	1	2	6	24
Stack Depth	0	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does the function call itself multiple times before returning a value?

Because each call waits for the result of factorial(n-1) before it can multiply and return its own value, as shown in steps 1 to 4 in the execution_table.

What happens when n reaches 1 or 0?

The base case is reached, so the function returns 1 immediately without further recursion, as seen in step 4 of the execution_table.

How does the stack depth change during recursion?

Stack depth increases with each recursive call until the base case, then decreases as calls return, shown in the variable_tracker and execution_table stack depth column.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value of factorial(1)?

A 0

B 1

C Waiting

D Undefined

💡 Hint

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

At which step does the recursion start to return values back up the call stack?

A Step 5

B Step 4

C Step 1

D Step 8

💡 Hint

Look for the first 'Return from factorial' operation in the execution_table.

If the input n was 3 instead of 4, how would the maximum stack depth change?

A Increase by 1

B Stay the same

C Decrease by 1

D Double

💡 Hint

Compare the 'Stack Depth' values in variable_tracker for n=4 and imagine one less recursive call.

Concept Snapshot

Factorial Using Recursion:
- Base case: if n == 0 or 1, return 1
- Recursive case: return n * factorial(n-1)
- Calls build up until base case, then multiply back down
- Stack depth grows with calls, shrinks on returns
- Useful for problems defined by smaller subproblems

Full Transcript

This visualization shows how the factorial function uses recursion by calling itself with decreasing values of n until it reaches the base case of 0 or 1. Each call waits for the next call's result before multiplying and returning its own value. The call stack grows deeper with each recursive call and then unwinds as results return back up. The execution table tracks each call, argument, condition check, return value, and stack depth. The variable tracker shows how n, return values, and stack depth change step-by-step. Key moments clarify why recursion waits for deeper calls, what happens at the base case, and how stack depth changes. The quiz tests understanding of return values, recursion unwinding, and stack depth changes. This method is a classic example of solving problems by breaking them into smaller identical problems.