Factorial Using Recursion in DSA C#

Mental Model

A function calls itself with a smaller number until it reaches 1, then multiplies all those numbers back up.

Analogy: Imagine stacking blocks from 1 up to n. To find the total height, you ask the block below how tall the stack is, then add your own height.

n=4
4! -> 4 x 3!
3! -> 3 x 2!
2! -> 2 x 1!
1! -> 1 (base case)

Dry Run Walkthrough

Input: Calculate factorial of 4

Goal: Find 4! = 4 x 3 x 2 x 1 = 24 using recursion

Step 1: Call factorial(4), which calls factorial(3)

factorial(4) waiting for factorial(3)

Why: We reduce the problem by one to reach the base case

Step 2: Call factorial(3), which calls factorial(2)

factorial(3) waiting for factorial(2)

Why: Keep breaking down until base case

Step 3: Call factorial(2), which calls factorial(1)

factorial(2) waiting for factorial(1)

Why: Continue reducing the problem

Step 4: Call factorial(1), base case reached, return 1

factorial(1) returns 1

Why: Base case stops recursion

Step 5: factorial(2) returns 2 x 1 = 2

factorial(2) returns 2

Why: Multiply current number by result of smaller problem

Step 6: factorial(3) returns 3 x 2 = 6

factorial(3) returns 6

Why: Multiply current number by result of smaller problem

Step 7: factorial(4) returns 4 x 6 = 24

factorial(4) returns 24

Why: Multiply current number by result of smaller problem

Result:

24

Annotated Code

DSA C#

using System;

class Program
{
    static int Factorial(int n)
    {
        if (n <= 1) // base case stops recursion
            return 1;
        return n * Factorial(n - 1); // recursive call with smaller number
    }

    static void Main()
    {
        int number = 4;
        int result = Factorial(number);
        Console.WriteLine(result);
    }
}

if (n <= 1) // base case stops recursion

stop recursion when n is 1 or less

return n * Factorial(n - 1); // recursive call with smaller number

multiply current n by factorial of n-1

Output

24

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) due to the call stack holding n recursive calls

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to understand for factorial

Edge Cases

n = 0

Returns 1 as factorial of 0 is defined as 1

DSA C#

if (n <= 1) // base case stops recursion

n = 1

Returns 1 immediately as base case

DSA C#

if (n <= 1) // base case stops recursion

n < 0

Function returns 1 due to base case but factorial is undefined for negatives; no error handling

DSA C#

if (n <= 1) // base case stops recursion

When to Use This Pattern

When you see a problem that can be broken down into smaller versions of itself, use recursion to solve it step by step.

Common Mistakes

Mistake: Missing base case causes infinite recursion and stack overflow
Fix: Add a base case like 'if (n <= 1) return 1;' to stop recursion

Mistake: Calling factorial with n-1 but forgetting to multiply by n
Fix: Return 'n * Factorial(n - 1)' to accumulate the product

Summary

Calculates factorial of a number by calling itself with smaller numbers until 1.

Use recursion when a problem can be divided into smaller identical problems.

The key is the base case that stops recursion and the multiplication that builds the answer back up.

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