Factorial Using Recursion in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Factorial Function Call

What is the output of the following C++ code that calculates factorial using recursion?

DSA C++

#include <iostream>

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

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

A 24

B 120

C 0

D 1

💡 Hint

Recall factorial of 4 is 4 * 3 * 2 * 1.

The factorial function multiplies n by factorial of n-1 until n is 0, where it returns 1. So factorial(4) = 4*3*2*1 = 24.

❓ Predict Output

intermediate

Output When Calling Factorial with Zero

What will be printed when the factorial function is called with 0?

DSA C++

#include <iostream>

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

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

A Undefined behavior

B 0

C 1

D Stack overflow

💡 Hint

Factorial of zero is defined as 1.

By definition, factorial(0) returns 1 as the base case in the recursion.

🔧 Debug

advanced

Identify the Error in Recursive Factorial Code

What error will this code produce when compiled and run?

DSA C++

#include <iostream>

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

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

A Stack overflow due to infinite recursion

B Returns 6 correctly

C Compilation error: missing return statement

D Returns 0

💡 Hint

Check the recursive call argument and base case.

The recursive call increases n instead of decreasing, so the base case is never reached, causing infinite recursion and stack overflow.

🧠 Conceptual

advanced

Why is Base Case Important in Recursive Factorial?

What is the main purpose of the base case in a recursive factorial function?

A To initialize the factorial value

B To multiply the numbers correctly

C To optimize the function for speed

D To stop the recursion and prevent infinite calls

💡 Hint

Think about what happens if recursion never stops.

The base case stops the recursion by providing a condition where the function returns without calling itself again.

❓ Predict Output

expert

Output of Factorial with Negative Input

What will happen when the factorial function below is called with -1?

DSA C++

#include <iostream>

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

int main() {
    std::cout << factorial(-1) << std::endl;
    return 0;
}

A Compilation error

B Stack overflow due to infinite recursion

C -1

D 1

💡 Hint

Consider what happens when n is negative and base case is only for zero.

Since the base case only stops recursion at n == 0, negative inputs cause the function to call factorial with decreasing n indefinitely, causing stack overflow.

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