Factorial Using Recursion in DSA C++ - Build from Scratch

Factorial Using Recursion

📖 Scenario: Imagine you want to calculate the factorial of a number, which is the product of all positive integers up to that number. For example, factorial of 4 is 4 x 3 x 2 x 1 = 24.We will use a simple function that calls itself to find the factorial, just like how you might ask a friend to help you with a smaller part of the problem until it becomes very easy.

🎯 Goal: Build a C++ program that calculates the factorial of a given number using recursion.

📋 What You'll Learn

Create a function called factorial that takes an integer parameter n.

Use recursion inside the factorial function to calculate the factorial.

Handle the base case when n is 0 or 1.

Call the factorial function with the number 5 and store the result.

Print the result to the console.

💡 Why This Matters

🌍 Real World

Calculating factorials is useful in math problems, probability, and combinatorics where you count arrangements or combinations.

💼 Career

Understanding recursion is important for many programming jobs, especially those involving algorithms, data structures, and problem solving.

1

Create the factorial function declaration

Write the function declaration for factorial that takes an integer n and returns an integer.

DSA C++

// Declare the factorial function
int factorial(int n);

Hint

Start by declaring the function so the compiler knows about it before main.

2

Define the factorial function with base case

Define the factorial function. If n is 0 or 1, return 1 as the base case.

DSA C++

#include 

int factorial(int n) {
    // Add base case here
}

int main() {
    return 0;
}

Hint

The base case stops the recursion. Factorial of 0 or 1 is 1.

3

Add recursive call in factorial function

In the factorial function, add a return statement that returns n multiplied by factorial(n - 1).

DSA C++

#include 

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    // Add recursive call here
}

int main() {
    return 0;
}

Hint

Each call multiplies n by the factorial of one less than n.

4

Call factorial and print the result

In main, call factorial(5), store the result in an integer variable called result, and print result using std::cout.

DSA C++

#include 

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

int main() {
    // Call factorial(5) and print the result
    // Your code here
}

Hint

Store the factorial of 5 in result and print it with std::cout.

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