Recursion Base Case and Recursive Case in DSA Java

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it knows how to solve directly.

Analogy: Imagine stacking boxes: you keep opening smaller boxes inside until you find the smallest box with a gift inside. That smallest box is the base case, and opening each box is the recursive step.

problem -> smaller problem -> smaller problem -> base case (solved)
       ↑               ↑               ↑
    recursive       recursive       solved directly
      calls          calls

Dry Run Walkthrough

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

Goal: Find 3! = 3 x 2 x 1 by breaking it down recursively

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

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

Why: We reduce the problem from 3! to 2! to solve smaller parts

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

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

Why: Keep reducing until we reach the base case

Step 3: Call factorial(1), which hits base case and returns 1

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

Why: Base case stops recursion and returns a known value

Step 4: Return factorial(2) = 2 x factorial(1) = 2 x 1 = 2

factorial(3) -> 2

Why: Combine smaller result to build answer

Step 5: Return factorial(3) = 3 x factorial(2) = 3 x 2 = 6

6

Why: Final answer computed by combining all results

Result:

6

Annotated Code

DSA Java

public class Factorial {
    // Recursive method to calculate factorial
    public static int factorial(int n) {
        if (n == 0) { // base case
            return 1; // stop recursion here
        }
        // recursive case: multiply n by factorial of n-1
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int input = 3;
        int result = factorial(input);
        System.out.println(result);
    }
}

if (n == 0) {

check base case to stop recursion

return 1;

return known value for base case

return n * factorial(n - 1);

recursive call reduces problem size and combines result

Output

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 a loop and constant space O(1), but recursion is clearer for problems naturally defined by smaller subproblems

Edge Cases

Input is 1 (smallest factorial)

Base case triggers immediately and returns 1

DSA Java

if (n == 0) {

Input is 0 (factorial of zero)

Handled correctly as base case returning 1

DSA Java

if (n == 0) {

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a simple stopping point, use recursion with a base case and recursive case.

Common Mistakes

Mistake: Missing or incorrect base case causing infinite recursion
Fix: Add a clear base case that stops recursion with a known answer

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call works on a smaller input to approach the base case

Summary

Recursion solves problems by calling itself with smaller inputs until reaching a base case.

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

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

Practice

1. In recursion, what is the purpose of the base case?

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 the base case role

   The base case is the condition where recursion stops to avoid infinite calls.

2. Step 2: Differentiate base case from recursive case

   The recursive case calls the function again, but the base case ends recursion.

3. Final Answer:

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

4. Quick Check:

   Base case stops recursion [OK]

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

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls function again
• Ignoring base case leads to infinite recursion

2. Which of the following is the correct syntax for a base case in a recursive Java method that calculates factorial?

easy

A. if (n > 0) return n * factorial(n - 1);

B. return n * factorial(n + 1);

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

D. if (n == 1) factorial(n);

Solution

1. Step 1: Identify base case condition for factorial

   Factorial base case is when n equals 0, return 1.

2. Step 2: Check syntax correctness

   if (n == 0) return 1; correctly returns 1 when n == 0, stopping recursion.

3. Final Answer:

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

4. Quick Check:

   Base case for factorial is n == 0 [OK]

Hint: Base case returns fixed value, usually simplest input [OK]

Common Mistakes:

• Using wrong condition for base case
• Calling factorial with n + 1 causing infinite recursion
• Not returning a value in base case

3. What is the output of this Java code?

public class Test {
  public static int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
  }
  public static void main(String[] args) {
    System.out.println(sum(3));
  }
}

medium

A. StackOverflowError

B. 6

C. 0

D. 3

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 B

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

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

Common Mistakes:

• Confusing base case return value
• Adding n - 1 instead of n
• Expecting output 3 instead of sum

4. Identify the error in this recursive Java method for factorial:

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

medium

A. Base case returns 0 instead of 1

B. Recursive call uses n + 1 instead of n - 1

C. Missing return statement in recursive case

D. No base case defined

Solution

1. Step 1: Check base case return value

   Factorial base case should return 1 for n == 0, but code returns 0.

2. Step 2: Understand impact of wrong base case

   Returning 0 causes factorial to always be 0 after recursion.

3. Final Answer:

   Base case returns 0 instead of 1 -> Option A

4. Quick Check:

   Factorial base case must return 1 [OK]

Hint: Base case for factorial returns 1, not 0 [OK]

Common Mistakes:

• Returning 0 in base case
• Using wrong recursive call direction
• Forgetting return keyword

5. Given this recursive method to compute Fibonacci numbers:

public static int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

What is the output of fib(4) and explain why the base case is important here?

hard

A. 3; base case stops infinite recursion by returning n when n ≤ 1

B. 5; base case returns 0 always

C. 7; base case calls fib(0) and fib(1) repeatedly

D. StackOverflowError; no base case defined

Solution

1. Step 1: Calculate fib(4) using recursion

   fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0); fib(1)=1, fib(0)=0.

2. Step 2: Compute values step-by-step

   fib(2)=1+0=1; fib(3)=1+1=2; fib(4)=2+1=3. Base case returns n when n ≤ 1, stopping recursion.

3. Final Answer:

   3; base case stops infinite recursion by returning n when n ≤ 1 -> Option A

4. Quick Check:

   fib(4) = 3 with base case stopping recursion [OK]

Hint: Base case returns n when n ≤ 1 to stop recursion [OK]

Common Mistakes:

• Miscomputing fib(4) as 5 or 7
• Ignoring base case importance
• Assuming base case returns 0 always