Recursion Base Case and Recursive Case in DSA C++

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it can answer directly.

Analogy: Imagine a set of nested boxes where you open one box to find a smaller box inside, and you keep opening boxes until you find the smallest box with a note inside. That smallest box is the base case, and opening each box is the recursive step.

Start -> [Function calls itself with smaller input] -> ... -> Base case reached -> Return answers back up

Dry Run Walkthrough

Input: Calculate factorial of 3 (3!) using recursion

Goal: Find 3! by breaking it down into smaller factorial problems until reaching 1!

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

factorial(3) -> factorial(2) -> ...

Why: We reduce the problem from 3! to 2! to simplify

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

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

Why: Keep breaking down until base case

Step 3: Call factorial(1), base case reached, return 1

factorial(1) returns 1

Why: Base case stops recursion and starts returning values

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

factorial(2) returns 2

Why: Combine smaller result to build answer

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

factorial(3) returns 6

Why: Final answer computed by combining all results

Result:

factorial(3) = 6

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;
    return n * factorial(n - 1); // recursive case
}

int main() {
    int number = 3;
    cout << "factorial(" << number << ") = " << factorial(number) << endl;
    return 0;
}

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

stop recursion when problem is simplest (0! or 1!)

return n * factorial(n - 1); // recursive case

call function with smaller input to build solution

Output

factorial(3) = 6

Complexity Analysis

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

Space: O(n) due to the call stack holding n recursive calls

vs Alternative: Iterative approach uses O(1) space but recursion is clearer for problems naturally defined by smaller subproblems

Edge Cases

Input is 1 (smallest factorial)

Function returns 1 immediately without further calls

DSA C++

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

Input is 0 (factorial of zero)

Function returns 1 immediately without further calls

DSA C++

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

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a simple stopping point, use recursion with base and recursive cases.

Common Mistakes

Mistake: Missing or incorrect base case causing infinite recursion
Fix: Always define a clear base case that stops recursion

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call works on a smaller or simpler input

Summary

Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The base case stops recursion; the recursive case breaks the problem down step-by-step.

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