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: you keep adding one block on top until you reach the last block, then you count the total blocks by multiplying as you go back down.

factorial(4)
  ↓ calls factorial(3)
    ↓ calls factorial(2)
      ↓ calls factorial(1)
        returns 1
      returns 2 * 1 = 2
    returns 3 * 2 = 6
  returns 4 * 6 = 24

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 by one to reach the base case

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

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

Why: Keep reducing until base case 1

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

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

Why: Base case reached at factorial(1)

Step 4: factorial(1) returns 1

factorial(1) = 1

Why: Base case returns 1 to stop recursion

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

factorial(2) = 2

Why: Multiply current number by result of smaller problem

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

factorial(3) = 6

Why: Multiply current number by result of smaller problem

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

factorial(4) = 24

Why: Multiply current number by result of smaller problem

Result:

factorial(4) = 24

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 0 || n == 1) // base case
        return 1; // factorial of 0 and 1 is 1
    return n * factorial(n - 1); // recursive call with smaller number
}

int main() {
    int number = 4;
    cout << "Factorial of " << number << " is " << factorial(number) << endl;
    return 0;
}

if (n == 0 || n == 1) // base case

stop recursion when n reaches 0 or 1

return 1; // factorial of 0 and 1 is 1

return 1 as factorial(0) = 1 and factorial(1) = 1

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

multiply current n by factorial of n-1

Output

Factorial of 4 is 24

Complexity Analysis

Time: O(n) because the function calls itself n times until it reaches 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) // base case

Input is 0

Returns 1 immediately as base case, which is correct by definition

DSA C++

if (n == 0 || n == 1) // base case

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: Not defining a base case, causing infinite recursion
Fix: Add a base case like 'if (n == 0 || n == 1) return 1;' to stop recursion

Mistake: Calling factorial with n=0 without handling it
Fix: Add a base case for n == 0 returning 1

Summary

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

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

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

Practice

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

easy

A. The product of all positive integers up to that number

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

C. The number multiplied by 2

D. The number divided by 2

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

   Only The product of all positive integers up to that number correctly describes this product, others describe sum or unrelated operations.

3. Final Answer:

   The product of all positive integers up to that number -> Option A

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 or doubles the number
• Mixing factorial with addition

2. Which of the following is the correct base case for a recursive factorial function in C++?

easy

A. if (n == 1) return n + 1;

B. if (n == 1) return 0;

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

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

Solution

1. Step 1: Identify factorial base case

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

2. Step 2: Check options

   Only if (n == 0) return 1; returns 1 when n is 0, others return incorrect values.

3. Final Answer:

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

4. Quick Check:

   Base case 0! = 1 [OK]

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

Common Mistakes:

• Returning 0 for base case
• Using n == 1 but returning wrong value
• Missing base case causing infinite recursion

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

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

int main() {
  std::cout << factorial(4);
  return 0;
}

medium

A. 120

B. 24

C. 16

D. 10

Solution

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

   factorial(4) calls 4 * factorial(3), factorial(3) calls 3 * factorial(2), factorial(2) calls 2 * factorial(1), factorial(1) calls 1 * factorial(0), factorial(0) returns 1.

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 B

4. Quick Check:

   4! = 24 [OK]

Hint: Multiply down from n to 1 recursively [OK]

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Incorrect multiplication order

4. Identify the error in this recursive factorial function:

int factorial(int n) {
  if (n == 1) return 1;
  return n * factorial(n + 1);
}

medium

A. The function should return n + factorial(n - 1)

B. The base case should be n == 0, not n == 1

C. The recursive call should use n - 1, not n + 1

D. No error, the function is correct

Solution

1. Step 1: Analyze recursive call

   The function calls factorial(n + 1), which increases n each time, causing infinite recursion.

2. Step 2: Correct recursive call

   To reduce n towards base case, it should call factorial(n - 1) instead.

3. Final Answer:

   The recursive call should use n - 1, not n + 1 -> Option C

4. Quick Check:

   Recursive call must decrease n [OK]

Hint: Recursive calls must move toward base case [OK]

Common Mistakes:

• Increasing n in recursive call causing infinite loop
• Wrong base case value
• Using addition instead of multiplication

5. Consider this modified factorial function that returns 1 for n <= 1:

int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

What is the output of factorial(-3) and why?

hard

A. 1, because base case handles n <= 1

B. Stack overflow error due to infinite recursion

C. 0, because negative numbers return zero

D. Undefined behavior, function does not handle negatives

Solution

1. Step 1: Check base case condition

   The base case triggers if n <= 1, so for n = -3, it returns 1 immediately.

2. Step 2: Understand recursion behavior

   Since base case covers negative inputs, no recursion occurs and function returns 1 safely.

3. Final Answer:

   1, because base case handles n <= 1 -> Option A

4. Quick Check:

   Base case covers negatives, returns 1 [OK]

Hint: Base case with <= handles negatives safely [OK]

Common Mistakes:

• Assuming negative input causes infinite recursion
• Expecting error or zero for negative input
• Ignoring base case condition