Java | Recursion

Recursion solves a problem by reducing it to a smaller instance of the same problem. A safe recursive method has two visible parts: a base case that stops and a recursive step that makes measurable progress toward it. If either part is vague, the method risks a stack overflow or an incorrect result.

Define the Base Case

The base case is the smallest valid input whose answer is already known. Write it first and test it directly, because every larger call depends on that stop condition being correct.

Make Strict Progress

Every recursive call must move a parameter toward the base case. State exactly which value becomes smaller or simpler so termination is a property of the code, not an assumption.

Trust the Smaller Result

A recursive step should combine one local piece of work with the answer returned by the smaller subproblem. That keeps the implementation aligned with the mathematical definition of the problem.

Respect Stack Cost

Each call consumes stack space. Prefer an iterative loop when depth can be large or attacker-controlled, and validate inputs before a recursive call begins.

Worked Examples

Example 1: Sum a Small Range

Zero is the base case. Every later call reduces the value by one and combines its own number with the proven answer for the smaller range.

Java

public class Main {
    static int sumTo(int value) {
        if (value == 0) return 0;
        return value + sumTo(value - 1);
    }

    public static void main(String[] args) {
        System.out.println(sumTo(4));
    }
}

Expected Result

Example 2: Validate Before Recursing

Negative input is rejected at the boundary. The recursive method then only needs to reason about the domain where progress toward zero is guaranteed.

Java

public class Main {
    static int factorial(int value) {
        if (value < 0) throw new IllegalArgumentException("value");
        if (value <= 1) return 1;
        return value * factorial(value - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(4));
    }
}

Expected Result

Example 3: Stop at a String Boundary

The index moves toward the string length on every call. The base case handles the position just beyond the final character without accessing an invalid index.

Java

public class Main {
    static int countA(String value, int index) {
        if (index == value.length()) return 0;
        int here = value.charAt(index) == 'a' ? 1 : 0;
        return here + countA(value, index + 1);
    }

    public static void main(String[] args) {
        System.out.println(countA("java", 0));
    }
}

Expected Result

Build and Practice Plan

Build confidence by changing one rule at a time. Start with the normal case, make the expected value visible, then add the nearest boundary and a rejected input. Keep Java syntax in service of the contract: a program is useful only when its behavior remains understandable as inputs, scale and failure conditions change.

Step 1: create one normal case, one boundary case and one rejected or failure case for define the base case before expanding the implementation.
Step 2: create one normal case, one boundary case and one rejected or failure case for make strict progress before expanding the implementation.
Step 3: create one normal case, one boundary case and one rejected or failure case for trust the smaller result before expanding the implementation.
Step 4: create one normal case, one boundary case and one rejected or failure case for respect stack cost before expanding the implementation.

Design Review Questions

Before accepting a change, identify the valid values, the owner of mutable state, the behavior for missing or invalid input and the test that proves the important boundary. Keep I/O, storage and framework wiring outside the small Java rule until the local behavior is proven.

A clear result is better than a hidden side effect. Name the condition, return the calculation where possible and let the outer layer decide whether to print, store or transmit it.

Example 4: Make the input visible

Start by naming the value the next line depends on. This keeps the lesson input explicit before we apply a transformation or call an external boundary. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    public static void main(String[] args) {
        String lesson = "Java Recursion";
        System.out.println(lesson.toUpperCase());
    }
}

Expected Result

JAVA RECURSION

Try next: Replace the sample value with one from your own notes, predict the result, and then run it.

Example 5: Make the input visible

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    public static void main(String[] args) {
        String lesson = "Java Recursion";
        System.out.println(lesson.toUpperCase());
    }
}

Expected Result

JAVA RECURSION

Try next: Replace the sample value with one from your own notes, predict the result, and then run it.

Example 6: Make the input visible

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    public static void main(String[] args) {
        String lesson = "Java Recursion";
        System.out.println(lesson.toUpperCase());
    }
}

Expected Result

JAVA RECURSION

Try next: Replace the sample value with one from your own notes, predict the result, and then run it.

Example 7: Guard an empty boundary

A small guard makes the allowed and rejected path visible. We want a caller to receive an intentional result instead of discovering an unexplained failure later. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    static boolean accepted(String value) {
        return value != null && !value.isBlank();
    }

    public static void main(String[] args) {
        System.out.println(accepted("Java Recursion"));
    }
}

Expected Result

true

Try next: Try an empty value as well as the normal value and describe why the two outcomes differ.

Example 8: Keep the transformation pure

This step returns a value instead of mixing the rule with display or storage work. That separation gives us a small unit we can run, test, and reuse. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    static int doubleValue(int value) { return value * 2; }

    public static void main(String[] args) {
        System.out.println(doubleValue(6));
    }
}

Expected Result

Try next: Call the same rule twice with different inputs and confirm that each result depends only on its input.

Example 9: Make a branch deliberate

Use a named branch where the business rule changes. A future reader should be able to point at the condition and state the result for both sides. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    public static void main(String[] args) {
        int score = 7;
        String result = score >= 5 ? "ready" : "review";
        System.out.println(result);
    }
}

Expected Result

ready

Try next: Change the boundary value by one and explain exactly which branch becomes active.

Example 10: Use a collection without hidden mutation

Collections become safer when we can see which value is read, which value is derived, and whether the original collection remains owned by the caller. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> lessons = List.of("Java Recursion", "boundary");
        System.out.println(String.join(" | ", lessons));
    }
}

Expected Result

Java Recursion | boundary

Try next: Add one more item and predict the derived result before executing the code.

Example 11: Return a named outcome

A named outcome is easier to test than an implied side effect. We can now distinguish a successful path from a rejected path without guessing from console noise. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    record Outcome(String status, String lesson) {}

    public static void main(String[] args) {
        Outcome outcome = new Outcome("ready", "Java Recursion");
        System.out.println(outcome.status());
    }
}

Expected Result

ready

Try next: Rename the outcome in your own words while preserving the same success and failure rule.

Example 12: Trace a small loop

Work through one value at a time. The point is not to memorize syntax; it is to see how the accumulator or output changes after each repeatable step. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    public static void main(String[] args) {
        int total = 0;
        for (int value : new int[] {1, 2, 3}) total += value;
        System.out.println(total);
    }
}

Expected Result

Try next: Use a shorter collection first, then add one value and trace the extra iteration aloud.

Example 13: Keep display at the edge

The core rule prepares a value, while the outer line decides how to show it. That keeps the result usable by a UI, test, API, or command-line caller. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    static String display(String value) { return "Lesson: " + value; }

    public static void main(String[] args) {
        System.out.println(display("Java Recursion"));
    }
}

Expected Result

Lesson: Java Recursion

Try next: Change only the display text and verify that the underlying rule and result stay unchanged.

Example 14: Test the closest boundary

A useful example includes the nearest boundary, not only the happy path. We are making the behavior inspectable before a real caller relies on it. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    static int quantity(int value) {
        if (value < 1) throw new IllegalArgumentException("quantity must be positive");
        return value;
    }

    public static void main(String[] args) {
        System.out.println(quantity(1));
    }
}

Expected Result

Try next: Try the lowest supported value and then one value just outside the accepted range.

Example 15: Write a tiny regression check

A compact assertion turns the lesson into a repeatable promise. It helps us catch a changed rule before a larger program hides the source of the mistake. We are applying that habit while revisiting Java Recursion.

Keep the example small enough to trace. First predict the normal result; then change one input and explain the boundary result in your own words.

Java

public class Main {
    public static void main(String[] args) {
        String result = "Java Recursion".toUpperCase();
        if (!result.equals("JAVA RECURSION")) throw new AssertionError("contract failed");
        System.out.println("contract holds");
    }
}

Expected Result

contract holds

Try next: Deliberately change the expected value once, observe the failed check, and then restore the correct contract.

Common Mistakes

Avoid: treating define the base case as a syntax trick while leaving the domain rule, ownership or error behavior implicit.
Avoid: treating make strict progress as a syntax trick while leaving the domain rule, ownership or error behavior implicit.
Avoid: treating trust the smaller result as a syntax trick while leaving the domain rule, ownership or error behavior implicit.
Avoid: treating respect stack cost as a syntax trick while leaving the domain rule, ownership or error behavior implicit.

Interview Checklist

State the input domain and the boundary value before explaining the syntax.
Explain the failure or rejected-input outcome rather than assuming the happy path.
Identify mutation, ownership and any value that must not be changed by a caller.
Name a focused test that would prove the rule still holds after a future change.
Separate the local Java decision from printing, persistence, networking or framework code.