Why Factorial Using Recursion in DSA C#?

The Big Idea

What if a function could solve a big problem by simply calling itself again and again?

The Scenario

Imagine you want to find the factorial of a number, like 5! (which means 5 x 4 x 3 x 2 x 1). Doing this by hand or writing code that multiplies each number one by one can get long and confusing, especially for bigger numbers.

The Problem

Manually writing code to multiply all numbers up to n means repeating similar steps again and again. It's easy to make mistakes, and the code becomes long and hard to read. Also, if you want to change the number, you might have to rewrite or copy-paste code.

The Solution

Recursion solves this by letting the function call itself with a smaller number each time. This way, the code stays short and clear. The function keeps calling itself until it reaches the simplest case (like 1), then it builds the answer back up automatically.

Before vs After

✗ Before

int factorial = 1;
for (int i = 1; i <= 5; i++)
{
    factorial *= i;
}

✓ After

int Factorial(int number)
{
    if (number <= 1) return 1;
    return number * Factorial(number - 1);
}

What It Enables

Recursion lets you solve complex problems with simple, elegant code that naturally breaks down tasks into smaller steps.

Real Life Example

Calculating combinations in a card game or arranging items in different orders often uses factorials, and recursion makes these calculations easy to write and understand.

Key Takeaways

Manual multiplication is repetitive and error-prone.

Recursion breaks the problem into smaller, manageable calls.

Recursive factorial code is shorter, clearer, and easier to maintain.

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