Factorial Using Recursion in DSA C++ - Execution Trace

Concept Flow - Factorial Using Recursion

Call factorial(n)

↓

Is n <= 1?

Yes→Return 1

No↓

Call factorial(n-1)

↓

Multiply n * factorial(n-1)

↓

Return result

The function calls itself with n-1 until it reaches 1, then returns 1 and multiplies back up.

Execution Sample

DSA C++

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

int main() {
  int result = factorial(4);
  return 0;
}

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

Execution Table

Step	Call	n	Action	Return Value	Stack Depth
1	factorial(4)	4	Check n>1, call factorial(3)		1
2	factorial(3)	3	Check n>1, call factorial(2)		2
3	factorial(2)	2	Check n>1, call factorial(1)		3
4	factorial(1)	1	n<=1, return 1	1	4
5	factorial(2)	2	Return 2 * 1	2	3
6	factorial(3)	3	Return 3 * 2	6	2
7	factorial(4)	4	Return 4 * 6	24	1
8	main		Result = 24	24	0

💡 Recursion ends when n <= 1, then returns multiply results back up the call stack.

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

Key Moments - 3 Insights

Why does the function call itself with n-1 before returning a value?

Because factorial(n) depends on factorial(n-1), so it must wait for factorial(n-1) to return before multiplying (see steps 1-4 in execution_table).

What stops the recursion from going forever?

The base case n <= 1 returns 1 without further calls (step 4), stopping recursion.

Why does the stack depth increase and then decrease?

Each recursive call adds a new layer to the call stack (steps 1-4), then returns remove layers as results multiply back up (steps 5-7).

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of factorial(2) at step 5?

A 1

B 2

C 6

D 24

💡 Hint

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

At which step does the recursion reach its base case?

A Step 1

B Step 7

C Step 4

D Step 8

💡 Hint

Look for the step where n <= 1 and return 1 happens in execution_table.

If factorial(5) was called instead of factorial(4), what would the stack depth be at the base case?

A It would be 5

B It would be 4

C It would be 6

D It would remain 1

💡 Hint

Stack depth equals the number of active calls; factorial(4) has depth 4 at base case (step 4).

Concept Snapshot

Factorial Using Recursion:
- Base case: if n <= 1, return 1
- Recursive case: return n * factorial(n-1)
- Calls build up stack until base case
- Returns multiply results back up
- Stack depth shows recursion depth

Full Transcript

This visualization shows how factorial is calculated using recursion. The function calls itself with n-1 until it reaches the base case where n is 1 or less, returning 1. Then each call returns its result multiplied by n, building the final factorial value. The execution table tracks each call, the current n, actions, return values, and stack depth. The variable tracker shows how n and return values change step by step. Key moments clarify why recursion stops and how the call stack grows and shrinks. The quiz tests understanding of return values, base case, and stack depth changes.

Practice

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

easy

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

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

C. The number multiplied by 2

D. The number divided by 2

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

   Only The product of all positive integers up to that number correctly describes this product, others describe sum or unrelated operations.

3. Final Answer:

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

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides or doubles the number
• Mixing factorial with addition

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

easy

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

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

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

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

Solution

1. Step 1: Identify factorial base case

   By definition, 0! = 1, so the base case must return 1 when n is 0.

2. Step 2: Check options

   Only if (n == 0) return 1; returns 1 when n is 0, others return incorrect values.

3. Final Answer:

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

4. Quick Check:

   Base case 0! = 1 [OK]

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

Common Mistakes:

• Returning 0 for base case
• Using n == 1 but returning wrong value
• Missing base case causing infinite recursion

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

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

int main() {
  std::cout << factorial(4);
  return 0;
}

medium

A. 120

B. 24

C. 16

D. 10

Solution

1. Step 1: Trace recursive calls for factorial(4)

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

2. Step 2: Calculate values bottom-up

   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 B

4. Quick Check:

   4! = 24 [OK]

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

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Incorrect multiplication order

4. Identify the error in this recursive factorial function:

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

medium

A. The function should return n + factorial(n - 1)

B. The base case should be n == 0, not n == 1

C. The recursive call should use n - 1, not n + 1

D. No error, the function is correct

Solution

1. Step 1: Analyze recursive call

   The function calls factorial(n + 1), which increases n each time, causing infinite recursion.

2. Step 2: Correct recursive call

   To reduce n towards base case, it should call factorial(n - 1) instead.

3. Final Answer:

   The recursive call should use n - 1, not n + 1 -> Option C

4. Quick Check:

   Recursive call must decrease n [OK]

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

Common Mistakes:

• Increasing n in recursive call causing infinite loop
• Wrong base case value
• Using addition instead of multiplication

5. Consider this modified factorial function that returns 1 for n <= 1:

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

What is the output of factorial(-3) and why?

hard

A. 1, because base case handles n <= 1

B. Stack overflow error due to infinite recursion

C. 0, because negative numbers return zero

D. Undefined behavior, function does not handle negatives

Solution

1. Step 1: Check base case condition

   The base case triggers if n <= 1, so for n = -3, it returns 1 immediately.

2. Step 2: Understand recursion behavior

   Since base case covers negative inputs, no recursion occurs and function returns 1 safely.

3. Final Answer:

   1, because base case handles n <= 1 -> Option A

4. Quick Check:

   Base case covers negatives, returns 1 [OK]

Hint: Base case with <= handles negatives safely [OK]

Common Mistakes:

• Assuming negative input causes infinite recursion
• Expecting error or zero for negative input
• Ignoring base case condition