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 smaller values 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 result = factorial(4);
Console.WriteLine(result);

Calculates factorial of 4 by calling itself recursively until base case.

Execution Table

Step	Call	n	Condition (n <= 1)?	Action	Return Value	Stack Depth
1	factorial(4)	4	False	Call factorial(3)		1
2	factorial(3)	3	False	Call factorial(2)		2
3	factorial(2)	2	False	Call factorial(1)		3
4	factorial(1)	1	True	Return 1	1	4
5	factorial(2)	2	False	Return 2 * 1	2	3
6	factorial(3)	3	False	Return 3 * 2	6	2
7	factorial(4)	4	False	Return 4 * 6	24	1
8	Main			Print 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	3	2	1	2	3	4	4	4
Return Value				1	2	6	24	24	24
Stack Depth	0	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does factorial(1) return 1 immediately without further calls?

Because the condition n <= 1 is true at step 4 in the execution_table, so it hits the base case and returns 1 to stop recursion.

How does the multiplication happen after the base case returns?

After step 4 returns 1, each previous call multiplies n by the returned value (steps 5 to 7), building the final result as shown in the Return Value column.

What does stack depth represent in recursion?

Stack depth shows how many recursive calls are active at each step; it increases when calling factorial(n-1) and decreases when returning results, as seen in the Stack Depth row.

Visual Quiz - 3 Questions

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

A 2

B 1

C 6

D 24

💡 Hint

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

At which step does the recursion reach its base case?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Look for the step where Condition (n <= 1)? is True in the execution_table.

If we call factorial(3) instead of factorial(4), what would be the final return value?

A 3

B 24

C 6

D 1

💡 Hint

Refer to the Return Value column for factorial(3) at step 6 in the execution_table.

Concept Snapshot

Factorial Using Recursion:
- Base case: if n <= 1, return 1
- Recursive case: return n * factorial(n-1)
- Calls stack up until base case, then multiply back down
- Stack depth shows active calls
- Result is product of all integers from n down to 1

Full Transcript

This visualization shows how factorial is calculated using recursion. The function calls itself with smaller values until it reaches the base case where n is 1 or less, returning 1. Then each call multiplies n by the returned value from the smaller call, building the final factorial result. The execution table tracks each call, condition check, action, return value, and stack depth. The variable tracker shows how n, return values, and stack depth change step-by-step. Key moments clarify why the base case stops recursion, how multiplication happens after returns, and what stack depth means. The quiz tests understanding of return values, base case step, and effect of changing input. This method uses the call stack to solve factorial elegantly and clearly.

Practice

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

easy

A. The number multiplied by 2

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

C. The number divided 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 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 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 multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides the number
• Assuming factorial doubles the number

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 1;

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

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

Solution

1. Step 1: Identify factorial base case

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

2. Step 2: Check options

   Only if (n == 0) return 1; returns 1 when n == 0, which is correct base case for recursion.

3. Final Answer:

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

4. Quick Check:

   Base case: 0! = 1 [OK]

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

Common Mistakes:

• Using n == 1 as base case
• Returning wrong value in base case
• Not handling negative inputs

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

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

Console.WriteLine(Factorial(4));

medium

A. 24

B. 10

C. 16

D. 120

Solution

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

   Factorial(4) = 4 * Factorial(3) Factorial(3) = 3 * Factorial(2) Factorial(2) = 2 * Factorial(1) Factorial(1) = 1 * Factorial(0) Factorial(0) = 1 (base case)

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 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
• Misunderstanding base case

4. Identify the error in this recursive factorial function:

static int Factorial(int n) {
    if (n == 1) return 1;
    return n * Factorial(n);
}

medium

A. Return type should be void

B. Missing base case for n == 0

C. Recursive call uses same n, causing infinite recursion

D. Multiplication operator is incorrect

Solution

1. Step 1: Analyze recursive call

   The function calls Factorial(n) inside itself without changing n, causing infinite recursion.

2. Step 2: Identify fix

   Recursive call should be Factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses same n, causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive call must change parameter to approach base case [OK]

Common Mistakes:

• Calling function with same argument
• Forgetting base case
• Wrong return type

5. How would you modify the recursive factorial function to handle negative inputs by returning -1 for any negative number?

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

hard

A. No change needed; factorial works for negatives

B. Add if (n < 0) return -1; before base case

C. Add if (n == 1) return -1; after base case

D. Change base case to if (n <= 0) return 1;

Solution

1. Step 1: Understand negative input handling

   Factorial is undefined for negative numbers, so function should return -1 for n < 0.

2. Step 2: Modify function

   Add a check at start: if (n < 0) return -1; before base case to handle negatives properly.

3. Final Answer:

   Add if (n < 0) return -1; before base case -> Option B

4. Quick Check:

   Return -1 for negatives before recursion [OK]

Hint: Check negatives first, return -1 before recursion [OK]

Common Mistakes:

• Changing base case incorrectly
• Not handling negatives at all
• Returning wrong value for negatives