Recursion Base Case and Recursive Case in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What is the output of the following C++ code when calling factorial(4)?

DSA C++

#include <iostream>
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

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

A 24

B 0

C 10

D 120

💡 Hint

Remember factorial of 0 is 1 and factorial(n) = n * factorial(n-1).

The factorial of 4 is 4 * 3 * 2 * 1 = 24. The base case returns 1 when n is 0.

❓ Predict Output

intermediate

Output of Recursive Sum Function

What is the output of this C++ code when calling sum(3)?

DSA C++

#include <iostream>
int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n - 1);
}

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

A 0

B 6

C 3

D 9

💡 Hint

Sum from 1 to n is n*(n+1)/2.

sum(3) = 3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0 = 6.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Function

What error will occur when running this C++ code?

DSA C++

#include <iostream>
int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 3);
}

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

A Output is 5

B Output is 3

C Stack overflow due to infinite recursion

D Compilation error

💡 Hint

Check the recursive calls and base cases carefully.

The function calls fibonacci(n-3) without a base case for n < 0, causing infinite recursion and stack overflow.

🧠 Conceptual

advanced

Understanding Base Case Importance

Why is the base case essential in a recursive function?

A It helps in looping through data

B It makes the function run faster

C It initializes variables before recursion

D It stops the recursion to prevent infinite calls

💡 Hint

Think about what happens if recursion never stops.

Without a base case, recursion would continue indefinitely, causing a stack overflow error.

❓ Predict Output

expert

Output of Recursive String Reverse Function

What is the output of this C++ code when calling reverse("abc")?

DSA C++

#include <iostream>
#include <string>

std::string reverse(const std::string& s) {
    if (s.empty()) return "";
    return reverse(s.substr(1)) + s[0];
}

int main() {
    std::cout << reverse("abc");
    return 0;
}

A cba

B abc

C bac

D cab

💡 Hint

The function moves the first character to the end after reversing the rest.

The function takes the first character off and appends it after reversing the rest, effectively reversing the string.

Practice

1. What is the purpose of the base case in a recursive function?

easy

A. To print the result of the recursion

B. To call the function again with a smaller input

C. To increase the input size for the next call

D. To stop the recursion and prevent infinite calls

Solution

1. Step 1: Understand recursion basics

   Recursion works by calling itself repeatedly until a stopping point is reached.

2. Step 2: Identify the role of base case

   The base case stops further recursive calls to avoid infinite loops.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option D

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case stops recursion to avoid infinite loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls recursion again
• Ignoring the need for a stopping condition

2. Which of the following is the correct syntax for a base case in this recursive function to calculate factorial?

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

easy

A. n > 0

B. n == 0

C. n == 1

D. n < 0

Solution

1. Step 1: Identify factorial base case

   Factorial of 0 is defined as 1, so base case is when n == 0.

2. Step 2: Check options for correct base case

   n == 0 matches n == 0, which returns 1 stopping recursion correctly.

3. Final Answer:

   n == 0 -> Option B

4. Quick Check:

   Factorial base case = n == 0 [OK]

Hint: Factorial base case is n equals zero [OK]

Common Mistakes:

• Using n > 0 as base case causes infinite recursion
• Using n < 0 which is invalid for factorial
• Confusing base case with recursive case

3. What will be the output of the following code?

int sum(int n) {
  if (n == 0) return 0;
  return n + sum(n - 1);
}

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

medium

A. 0

B. 3

C. 6

D. Error

Solution

1. Step 1: Trace recursive calls for sum(3)

   sum(3) = 3 + sum(2), sum(2) = 2 + sum(1), sum(1) = 1 + sum(0), sum(0) = 0.

2. Step 2: Calculate total sum

   sum(3) = 3 + 2 + 1 + 0 = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum 1 to 3 = 6 [OK]

Hint: Sum from n to 0 adds all numbers [OK]

Common Mistakes:

• Returning n instead of n + sum(n-1)
• Missing base case causing infinite recursion
• Confusing output with just n

4. Identify the error in this recursive function to find factorial:

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

medium

A. Recursive call increases n, causing infinite recursion

B. Function should return void, not int

C. Missing return statement in base case

D. Base case should be n == 0, not n == 1

Solution

1. Step 1: Analyze recursive call

   The function calls factorial(n + 1), which increases n each time, never reaching base case.

2. Step 2: Identify infinite recursion cause

   Because n grows, base case n == 1 is never met, causing infinite recursion.

3. Final Answer:

   Recursive call increases n, causing infinite recursion -> Option A

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive calls must reduce input to reach base case [OK]

Common Mistakes:

• Increasing n instead of decreasing in recursion
• Wrong base case value
• Ignoring infinite recursion risk

5. You want to write a recursive function to compute the nth Fibonacci number where fib(0) = 0 and fib(1) = 1. Which of the following correctly defines the base cases and recursive case?

hard

A. if (n == 0) return 0; if (n == 1) return 1; else return fib(n - 1) + fib(n - 2);

B. if (n == 1) return 0; if (n == 2) return 1; else return fib(n - 1) + fib(n - 2);

C. if (n <= 1) return n; else return fib(n + 1) + fib(n - 2);

D. if (n == 0) return 1; if (n == 1) return 1; else return fib(n - 1) + fib(n - 2);

Solution

1. Step 1: Identify correct base cases for Fibonacci

   By definition, fib(0) = 0 and fib(1) = 1 are base cases.

2. Step 2: Check recursive case correctness

   Recursive case sums fib(n-1) and fib(n-2), matching Fibonacci definition.

3. Final Answer:

   if (n == 0) return 0; if (n == 1) return 1; else return fib(n - 1) + fib(n - 2); -> Option A

4. Quick Check:

   Fibonacci base and recursive cases match definition [OK]

Hint: Base cases fib(0)=0, fib(1)=1; recursive sums previous two [OK]

Common Mistakes:

• Wrong base case values
• Increasing n in recursive calls
• Returning wrong values for base cases