Why Factorial Using Recursion in DSA C?

The Big Idea

What if a function could solve a big problem by solving smaller versions of 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 means multiplying all numbers one by one, which is okay for small numbers but gets tiring and slow for bigger numbers.

The Problem

Manually multiplying each number takes a lot of time and is easy to make mistakes, especially if the number is large. Writing code that repeats the same steps again and again can be long and confusing.

The Solution

Recursion lets the function call itself to solve smaller parts of the problem, breaking down the factorial calculation into simpler steps automatically. This makes the code shorter, cleaner, and easier to understand.

Before vs After

✗ Before

int factorial(int number) {
    int result = 1;
    for (int i = 1; i <= number; i++) {
        result *= i;
    }
    return result;
}

✓ After

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

What It Enables

Recursion enables solving complex problems by breaking them into smaller, easier problems that the computer can handle naturally.

Real Life Example

Calculating combinations in probability, where factorials are used to find how many ways to choose items from a group, is easier with recursion.

Key Takeaways

Manual multiplication is slow and error-prone for large numbers.

Recursion breaks the problem into smaller parts automatically.

Recursive factorial code is cleaner and easier to read.

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