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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Factorial Function

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

DSA Java

public class Main {
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
    public static void main(String[] args) {
        System.out.println(factorial(4));
    }
}

A 0

B 10

C 24

D 120

💡 Hint

Remember 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 of Recursive Sum Function

What is printed when the following Java code runs sum(3)?

DSA Java

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

A 6

B 3

C 0

D 10

💡 Hint

Sum from 1 to 3 is 1 + 2 + 3.

The function adds n to the sum of numbers from 1 to n-1 until it reaches 1, returning 1. So sum(3) = 3 + 2 + 1 = 6.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Function

What error will occur when running this Java code?

DSA Java

public class Main {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    public static void main(String[] args) {
        System.out.println(fibonacci(-1));
    }
}

A StackOverflowError

B 0

C 1

D IllegalArgumentException

💡 Hint

Think about what happens when n is negative.

The function does not handle negative inputs, so calling fibonacci(-1) causes infinite recursion leading to StackOverflowError.

❓ Predict Output

advanced

Output of Recursive String Reversal

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

DSA Java

public class Main {
    public static String reverse(String s) {
        if (s.isEmpty()) {
            return s;
        } else {
            return reverse(s.substring(1)) + s.charAt(0);
        }
    }
    public static void main(String[] args) {
        System.out.println(reverse("abc"));
    }
}

A bac

B cba

C abc

D cab

💡 Hint

The function moves the first character to the end recursively.

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

🧠 Conceptual

expert

Understanding Base Case Importance in Recursion

Why is the base case essential in a recursive function?

A It initializes variables used in the recursive calls.

B It makes the function run faster by skipping some steps.

C It allows the function to call itself multiple times simultaneously.

D It stops the recursion to prevent infinite calls and eventually returns a result.

💡 Hint

Think about what happens if recursion never stops.

The base case stops the recursion by providing a simple answer without further calls, preventing infinite loops and stack overflow.

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