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.

Practice

1. What does the factorial of a number represent in mathematics?

easy

A. The number divided by 2

B. The sum of all positive integers up to that number

C. The number multiplied by 2

D. The product of all positive integers up to that number

Solution

1. Step 1: Understand factorial definition

   Factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

2. Step 2: Compare options with definition

   Only The product of all positive integers up to that number correctly describes factorial as a product, not sum or division.

3. Final Answer:

   The product of all positive integers up to that number -> Option D

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial means multiply all numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides the number
• Mixing multiplication with addition

2. Which of the following is the correct base case for a recursive factorial function in C?

easy

A. if (n == 0) return 1;

B. if (n == 1) return 0;

C. if (n == 0) return 0;

D. if (n == 1) return n + 1;

Solution

1. Step 1: Identify base case for factorial

   Factorial of 0 is defined as 1, so base case must return 1 when n is 0.

2. Step 2: Check options for correct base case

   if (n == 0) return 1; returns 1 when n is 0, which is correct. Others return wrong values or conditions.

3. Final Answer:

   if (n == 0) return 1; -> Option A

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Base case for factorial is n=0 returns 1 [OK]

Common Mistakes:

• Returning 0 for base case
• Using wrong condition like n==1
• Returning n+1 incorrectly

3. What is the output of the following C code?

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

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

medium

A. 24

B. 10

C. 16

D. 120

Solution

1. Step 1: Trace factorial(4) calls

   factorial(4) calls factorial(3), factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0).

2. Step 2: Calculate return values

   factorial(0) = 1
   factorial(1) = 1 * 1 = 1
   factorial(2) = 2 * 1 = 2
   factorial(3) = 3 * 2 = 6
   factorial(4) = 4 * 6 = 24

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Multiply down from n to 1 recursively [OK]

Common Mistakes:

• Stopping recursion too early
• Adding instead of multiplying
• Wrong base case causing infinite recursion

4. Identify the error in this recursive factorial function and select the fix:

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

medium

A. Change base case to if (n == 0) return 0;

B. Change recursive call to factorial(n - 1);

C. Remove base case entirely;

D. Change return to n + factorial(n - 1);

Solution

1. Step 1: Analyze recursive call

   The function calls factorial(n) inside itself without reducing n, causing infinite recursion.

2. Step 2: Correct recursive call to reduce n

   Changing call to factorial(n - 1) ensures n decreases each call, reaching base case.

3. Final Answer:

   Change recursive call to factorial(n - 1); -> Option B

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive calls must move toward base case [OK]

Common Mistakes:

• Calling factorial(n) again causing infinite loop
• Wrong base case value
• Using addition instead of multiplication

5. How would you modify a recursive factorial function to handle negative inputs by returning -1 for invalid input?
Choose the correct code snippet.

hard

A. if (n <= 0) return 1; else return n * factorial(n - 1);

B. if (n == 0) return -1; else return n * factorial(n - 1);

C. if (n < 0) return -1; else if (n == 0) return 1; else return n * factorial(n - 1);

D. if (n < 0) return 0; else return n * factorial(n - 1);

Solution

1. Step 1: Add check for negative input

   Factorial is not defined for negative numbers, so return -1 if n < 0.

2. Step 2: Keep base case and recursive call correct

   Return 1 if n == 0, else multiply n by factorial(n - 1).

3. Final Answer:

   if (n < 0) return -1; else if (n == 0) return 1; else return n * factorial(n - 1); -> Option C

4. Quick Check:

   Negative input returns -1 [OK]

Hint: Check negative input first, then proceed [OK]

Common Mistakes:

• Not handling negative input
• Returning wrong value for negatives
• Incorrect base case for zero