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 by first asking how many blocks are below, then adding the current one on top.

factorial(n)
  ↓
factorial(n-1)
  ↓
factorial(n-2)
  ↓
...
  ↓
factorial(1) = 1
  ↑
return multiply back up

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion

Goal: Find 4! = 4 x 3 x 2 x 1 = 24 by recursive calls

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

factorial(4) -> factorial(3) -> ?

Why: We reduce the problem to a smaller number to reach the base case

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

factorial(4) -> factorial(3) -> factorial(2) -> ?

Why: Keep breaking down until we reach factorial(1)

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

factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)

Why: Base case factorial(1) returns 1

Step 4: factorial(1) returns 1

factorial(1) = 1

Why: Base case reached, start returning values

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

factorial(2) = 2

Why: Multiply current number by result of smaller factorial

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

factorial(3) = 6

Why: Continue multiplying back up

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

factorial(4) = 24

Why: Final result is the factorial of 4

Result:

factorial(4) = 24

Annotated Code

DSA C

#include <stdio.h>

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // base case: factorial of 0 or 1 is 1
    }
    return n * factorial(n - 1); // recursive call multiplying current n
}

int main() {
    int num = 4;
    int result = factorial(num);
    printf("Factorial of %d is %d\n", num, result);
    return 0;
}

if (n == 0 || n == 1) {

check for base case to stop recursion

return 1; // base case: factorial of 0 or 1 is 1

return 1 when base case reached

return n * factorial(n - 1);

recursive call multiplying current number by factorial of smaller number

Output

Factorial of 4 is 24

Complexity Analysis

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

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 and write

Edge Cases

Input is 1

Returns 1 immediately as base case

DSA C

if (n == 0 || n == 1) {

Input is 0

Returns 1 immediately as base case

DSA C

if (n == 0 || n == 1) {

When to Use This Pattern

When you see a problem asking for repeated multiplication down to 1, use recursion to break it into smaller factorial calls.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add if (n == 0 || n == 1) return 1; to stop recursion

Summary

Calculates factorial by calling itself with smaller numbers until reaching 1.

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

The key is the base case that stops the recursion and starts returning results.

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