Recursion Base Case and Recursive Case in DSA Java - Build from Scratch

Recursion Base Case and Recursive Case

📖 Scenario: Imagine you have a stack of boxes, and you want to count how many boxes are in the stack. You can only look at the top box and then the rest of the stack below it. This is like a simple problem where recursion helps by breaking it down step-by-step.

🎯 Goal: You will write a recursive Java method to count the number of boxes in a stack represented by an integer. You will practice writing the base case and the recursive case clearly.

📋 What You'll Learn

Create a method called countBoxes that takes an integer n representing the number of boxes.

Write the base case for when there are no boxes left (n = 0).

Write the recursive case that calls countBoxes with one less box.

Print the total count of boxes returned by the recursive method.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like navigating folders, solving puzzles, and processing data structures like trees.

💼 Career

Understanding recursion is important for software development roles that involve algorithms, problem solving, and working with complex data structures.

1

Create the initial number of boxes

Create an integer variable called boxes and set it to 5 to represent the number of boxes in the stack.

DSA Java

# Your code here

Hint

Use int boxes = 5; to create the variable.

2

Add the recursive method signature

Add a public static method called countBoxes that takes an integer parameter n and returns an integer.

DSA Java

public class Main {
    public static void main(String[] args) {
        int boxes = 5;
    }

    // Define countBoxes method here
    
    // Your code here
}

Hint

Write the method header as public static int countBoxes(int n).

3

Write the base case and recursive case

Inside the countBoxes method, write the base case: if n == 0, return 0. Then write the recursive case: return 1 + countBoxes(n - 1).

DSA Java

public class Main {
    public static void main(String[] args) {
        int boxes = 5;
    }

    public static int countBoxes(int n) {
        // Write base case and recursive case here
        
        // Your code here
    }
}

Hint

The base case stops recursion when n is zero. The recursive case counts one box and calls itself with one less box.

4

Print the result of the recursive count

In the main method, add a print statement that calls countBoxes(boxes) and prints the result.

DSA Java

public class Main {
    public static void main(String[] args) {
        int boxes = 5;
        // Print the count of boxes here
        
        // Your code here
    }

    public static int countBoxes(int n) {
        if (n == 0) {
            return 0;
        } else {
            return 1 + countBoxes(n - 1);
        }
    }
}

Hint

Use System.out.println(countBoxes(boxes)); to print the result.

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