Java foundations · Lesson 21 About 60 min with practice

Java Recursion

Solve a small task by solving a smaller version of it. Trace the base case, the pending calls, and the results coming back—then decide when a loop is the clearer and safer choice.

Before you start: review returned results, per-call local state, and array indexes and empty cases. All source examples run with Java 21. Keep inputs within their stated small contracts; do not test missing progress by running unbounded self-calls.

What you will be able to do

Identify the base case and explain why recursive calls eventually reach it.
Trace work before a recursive call separately from work after it returns.
Keep each invocation's parameters and local results distinct.
Combine a smaller subproblem's result instead of discarding it.
Distinguish termination, numeric range, stack depth, and repeated-work costs.
Implement and test a bounded recursive calculation against a loop without mutating input.

A recursive method calls itself on a smaller task

A recursive method solves part of a problem by calling the same method for a smaller version of that problem. countDown(3) prints 3 and asks countDown(2) to handle the remaining countdown. That call prints 2 and asks countDown(1), which eventually reaches countDown(0).

The call with zero is the base case: it can finish without making another recursive call. The other calls are recursive cases. Their n - 1 argument makes the task smaller. You need both a stopping rule and a reason the permitted inputs will reach it; simply placing a self-call somewhere in a method is not a complete algorithm.

The example's contract restricts n to 0 through 20. Trace only small inputs while learning. The recursive call is an ordinary method call with a new parameter value, not a jump that secretly resets the caller's local variable. The calling invocation can still have work pending after its callee finishes.

JAVA 21 COMPILER

Main.java · Do work before the smaller call

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        countDown(3);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        countDown(3);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

Standard input · optional

INPUT BEFORE EXECUTIONProvide all input before selecting Run. Each line is sent to standard input; the stream then ends. This is not an interactive terminal, and input is not automatically echoed in the output. Reset restores the example source and input.

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

3
2
1
Done.

Work before and after the call happens in different orders

countUp uses the same smaller argument and zero base case but prints after its recursive call. countUp(3) must wait for countUp(2) before printing 3, and countUp(2) must wait for countUp(1). The zero call returns first, allowing the waiting calls to continue in reverse nesting order.

The print order is therefore 1, 2, 3, followed by the statement in main. Returning from the zero call does not end all other calls. It resumes the invocation that made that call, which can then print its own n and return to its caller.

When tracing recursion, mark the statements before the self-call, the call itself, and the statements afterward. Moving a println across the call changes the output order even when the inputs and base condition are identical. This is often easier to understand than starting with a large mathematical example.

JAVA 21 COMPILER

Main.java · Do work after the smaller call returns

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        countUp(3);
        System.out.println("Back in main.");
    }

    // Precondition: n is between 0 and 20.
    static void countUp(int n) {
        if (n == 0) {
            return;
        }
        countUp(n - 1);
        System.out.println(n);
    }
}

public class Main {
    public static void main(String[] args) {
        countUp(3);
        System.out.println("Back in main.");
    }

    // Precondition: n is between 0 and 20.
    static void countUp(int n) {
        if (n == 0) {
            return;
        }
        countUp(n - 1);
        System.out.println(n);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

1
2
3
Back in main.

Each invocation keeps its own parameters and pending result

sumTo(3) means add the integers from 1 through 3. It asks for sumTo(2), keeps its own n of 3, and waits to add that value to the smaller result. The n in the deeper call is 2; that does not overwrite the earlier invocation's n.

The trace prints every entry before showing any combined result. At zero, the method returns 0. The n = 1 invocation combines 1 + 0 and returns 1; the n = 2 invocation combines 2 + 1 and returns 3; the n = 3 invocation combines 3 + 3 and returns 6. main then prints the final total.

The JVM models method invocations with frames containing local working information. You can think of the nested pending calls as a call stack. No shared field is needed to remember the different n values. The trace output is intentional teaching instrumentation; a reusable calculation normally returns its result without printing each step.

JAVA 21 COMPILER

Main.java · Trace parameters going down and results coming back

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Total: " + sumTo(3));
    }

    // Precondition: n is between 0 and 20. Trace output is intentional here.
    static int sumTo(int n) {
        System.out.println("Enter: " + n);
        if (n == 0) {
            System.out.println("Base returns: 0");
            return 0;
        }
        int smaller = sumTo(n - 1);
        int result = n + smaller;
        System.out.println("Return from " + n + ": " + result);
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Total: " + sumTo(3));
    }

    // Precondition: n is between 0 and 20. Trace output is intentional here.
    static int sumTo(int n) {
        System.out.println("Enter: " + n);
        if (n == 0) {
            System.out.println("Base returns: 0");
            return 0;
        }
        int smaller = sumTo(n - 1);
        int result = n + smaller;
        System.out.println("Return from " + n + ": " + result);
        return result;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Enter: 3
Enter: 2
Enter: 1
Enter: 0
Base returns: 0
Return from 1: 1
Return from 2: 3
Return from 3: 6
Total: 6

Explain sumTo(3), one returning call at a time

sumTo(3) waits for sumTo(2).
sumTo(2) waits for sumTo(1), which waits for sumTo(0).
sumTo(0) returns the base result 0.
The n = 1 call returns 1 + 0 = 1.
The n = 2 call returns 2 + 1 = 3.
The n = 3 call returns 3 + 3 = 6 to main.

The two threes in the final addition have different roles: the current input is 3, and the smaller returned sum is also 3.

A base case is not a substitute for an input contract

A countdown whose base is n == 0 and whose step is n - 1 terminates as intended for nonnegative inputs. Starting at -1 instead moves to -2, -3, and farther away from the intended base. A base case exists in the source, but that does not make it reachable from every possible input.

The guarded example rejects negative and oversized input before starting the countdown. Zero remains valid and immediately prints Done. This separates invalid-input handling from the valid algorithm. Replacing every base condition with a broad comparison can hide invalid data by treating it as an ordinary completed task.

For each recursive case, identify a quantity that decreases toward a lower bound: remaining steps, remaining array elements, or remaining digits. Also check that your update cannot skip the intended stopping state. Review unsafe changes by tracing them rather than running an unbounded program and relying on a sandbox timeout.

JAVA 21 COMPILER

Main.java · Reject invalid input before recursion

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        int n = -1;
        if (n < 0 || n > 20) {
            System.out.println("Choose an integer from 0 through 20.");
            return;
        }
        countDown(n);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int n = -1;
        if (n < 0 || n > 20) {
            System.out.println("Choose an integer from 0 through 20.");
            return;
        }
        countDown(n);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Choose an integer from 0 through 20.

Test zero, one, and rejected input safely

Change n to 0: only Done. should print. Change it to 1: expect 1, then Done. Keep the guard when trying -1 or 21: each must print only the validation message rather than enter recursion.

The base result must fit the calculation

Factorial multiplies the integers from 1 through n. Its recursive rule is n times factorial(n - 1), but factorial(0) is 1. Returning zero at that base would make every positive factorial zero, even though the recursion still terminates normally.

For n = 5, the result is 5 * 4 * 3 * 2 * 1 * 1 = 120. The method returns long, and each multiplication combines n with a long recursive result. The caller limits n to 20 because 20! fits in long while 21! does not. Termination and numeric range are different correctness checks.

Test the base input itself, the next input, and a short normal case. For factorial those include 0, 1, and 5. Do not assume that the zero used as an empty sum is also appropriate for a product. The base result should explain the mathematical or domain meaning of the smallest valid task.

JAVA 21 COMPILER

Main.java · A valid base result depends on the operation

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        int n = 5;
        if (n < 0 || n > 20) {
            System.out.println("Factorial input must be 0..20.");
            return;
        }
        System.out.println(n + "! = " + factorial(n));
    }

    // Precondition: 0 <= n <= 20, so the result fits in long.
    static long factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int n = 5;
        if (n < 0 || n > 20) {
            System.out.println("Factorial input must be 0..20.");
            return;
        }
        System.out.println(n + "! = " + factorial(n));
    }

    // Precondition: 0 <= n <= 20, so the result fits in long.
    static long factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

5! = 120

A smaller subproblem does not always mean subtracting one

For a nonnegative integer, dividing by ten removes its final decimal digit. digitSum(507) separates the last digit 7 and asks digitSum(50) for the rest; that call separates 0 and asks digitSum(5). A single digit is already its own digit sum, so it forms the base case.

The results combine as 5, then 0 + 5, then 7 + 5, giving 12. Zero is handled directly by the same single-digit base. The depth follows the number of digits rather than the numeric magnitude; a nonnegative int has at most ten decimal digits.

This method's contract does not accept negative integers. Do not silently apply Math.abs to every int to extend it: Integer.MIN_VALUE has no positive counterpart representable as int. Supporting another domain requires a deliberate conversion and validation policy, not only another recursive call.

JAVA 21 COMPILER

Main.java · Reduce a nonnegative number by removing a digit

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Digit sum: " + digitSum(507));
        System.out.println("Zero digit sum: " + digitSum(0));
    }

    // Precondition: value is a nonnegative int.
    static int digitSum(int value) {
        if (value < 10) {
            return value;
        }
        return value % 10 + digitSum(value / 10);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Digit sum: " + digitSum(507));
        System.out.println("Zero digit sum: " + digitSum(0));
    }

    // Precondition: value is a nonnegative int.
    static int digitSum(int value) {
        if (value < 10) {
            return value;
        }
        return value % 10 + digitSum(value / 10);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Digit sum: 12
Zero digit sum: 0

Use a count to shrink the task without changing the data

sumPrefix(values, count) adds the first count elements. With count 3, it combines values[2] with the first two elements' sum. The smaller task uses the same array reference and count - 1; no array copy or element mutation is needed.

At count zero, the empty prefix sums to zero and no element is accessed. For a positive count, count - 1 is the last included position. The required bounds are 0 <= count <= values.length, plus the small depth bound used in this lesson. Reading an element before testing the empty case would break that safe boundary behavior.

The values themselves may be negative; count is what controls progress. The long result preserves sums beyond int range. Each recursive call receives copied parameter values, including a copied reference to the same array, but this implementation only reads that shared data. Recursion is not permission to change a caller's array unexpectedly.

JAVA 21 COMPILER

Main.java · Describe a smaller array prefix without copying it

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        int[] values = {4, -2, 7};
        System.out.println("Prefix total: " + sumPrefix(values, 3));
        System.out.println("Empty prefix: " + sumPrefix(values, 0));
    }

    // Preconditions: non-null values, 0 <= count <= values.length, count <= 64.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int[] values = {4, -2, 7};
        System.out.println("Prefix total: " + sumPrefix(values, 3));
        System.out.println("Empty prefix: " + sumPrefix(values, 0));
    }

    // Preconditions: non-null values, 0 <= count <= values.length, count <= 64.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Prefix total: 9
Empty prefix: 0

Which element belongs to count 3?

Index 2 is the last included element, so the result is 7 plus the first two entries' sum. The next count is 2, then 1, then 0. The array reference stays the same; the count changes the task being described. At zero, no element is read.

A loop can compute the same result with less call-stack depth

The recursive and iterative sum methods both add 1 through 5 and return 15. For this linear task, both do a number of additions proportional to n. The recursive version also keeps a chain of pending calls, while the loop uses one method invocation with a running local total.

For sumTo(n), the recursive chain includes n + 1 invocations when counting the zero base call. That extra active-call depth grows with n; the loop's working stack depth does not grow with the number of iterations. A short-looking recursive expression is not automatically more memory-efficient or faster.

Choose a loop for a long straightforward traversal unless recursion provides a clear structural advantage. Trees and divide-and-conquer problems can fit recursive descriptions naturally, but those structures come later. Java 21 does not guarantee tail-call elimination, so moving a recursive call to the end is not a portable promise of constant stack use.

JAVA 21 COMPILER

Main.java · Compare recursive and iterative sums

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Recursive: " + sumTo(5));
        System.out.println("Loop: " + sumToLoop(5));
    }

    // Precondition for both methods: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }

    static int sumToLoop(int n) {
        int total = 0;
        for (int value = 1; value <= n; value++) {
            total += value;
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Recursive: " + sumTo(5));
        System.out.println("Loop: " + sumToLoop(5));
    }

    // Precondition for both methods: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }

    static int sumToLoop(int n) {
        int total = 0;
        for (int value = 1; value <= n; value++) {
            total += value;
        }
        return total;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Recursive: 15
Loop: 15

Several recursive calls can repeat the same subproblem

The small Fibonacci example returns n for 0 or 1 and otherwise adds the previous two results. fibonacci(5) calls fibonacci(4) and fibonacci(3). But computing fibonacci(4) also calls fibonacci(3), so the same subproblem is recalculated in multiple branches.

The maximum nesting depth and the total amount of work are different measurements. This naive version has a linearly growing maximum depth but exponentially growing repeated work as n increases. A reachable base case does not by itself make a recursive algorithm efficient.

Keep the runnable example at its stated small input range, 0 through 10. For larger Fibonacci calculations, iteration or a deliberately cached solution is more appropriate; caching adds its own design decisions. Do not benchmark a large naive call in the website runner or interpret resource-limit termination as a valid answer.

JAVA 21 COMPILER

Main.java · Two smaller calls can repeat the same work

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("fib(5): " + fibonacci(5));
    }

    // Small teaching input only: 0 <= n <= 10. This is not an efficient implementation.
    static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("fib(5): " + fibonacci(5));
    }

    // Small teaching input only: 0 <= n <= 10. This is not an efficient implementation.
    static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

fib(5): 5

Find a repeated subproblem without increasing the input

fibonacci(5) requests fibonacci(4) and fibonacci(3). The fibonacci(4) branch requests fibonacci(3) again. The implementation does not remember the earlier answer for reuse. Keep the example small: large naive calls demonstrate resource consumption, not a better understanding of recursion.

Correct termination does not guarantee unlimited safe depth

An endlessly repeating self-call can exhaust the available call stack and produce StackOverflowError. A method with a mathematically valid base case can also recurse too deeply before reaching it. The stack is finite, and the depth that fits depends on the runtime configuration and the particular method.

This lesson uses deliberately bounded inputs. The lab's limit of 64 prefix elements is an exercise boundary, not a universal maximum or universal safe depth for every Java method. It makes the intended examples small and testable rather than inviting arbitrary-depth recursion.

Do not catch StackOverflowError as the normal stopping rule or increase resource limits to hide missing progress. First check validation, the base condition, the argument change, and whether an iterative design is better. Numeric overflow, repeated work, output volume, and stack exhaustion each need their own reasoning.

Repair exercise: keep the smaller returned result

This bounded recursive sum reaches zero but discards every smaller result. It returns 3 instead of 6 for input 3. Repair the combination step, keeping the zero base case and the decreasing argument.

JAVA 21 COMPILER

Main.java · Repair a lost smaller sum

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        sumTo(n - 1);
        return n;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        sumTo(n - 1);
        return n;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Reveal the explained repair

A method call can compute a value and still have that value ignored by its caller. The starter returns each current n without adding the smaller sum. Returning n + sumTo(n - 1) preserves that smaller result and combines it with the current contribution. Test 0 for the empty sum, 1 for the smallest positive sum, and 3 for the multi-call case; termination alone would not expose the lost-result bug.

JAVA 21 COMPILER

Main.java · Repaired recursive combination

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output

Sum: 6

Independent lab: sum a bounded prefix two ways

Build a bounded recursive prefix sum and compare it with a loop. The count describes how many leading elements to include, not the last index. Values may be positive, zero, or negative. Edit data in source; the report is a local console exercise, not stored application data.

Implement static boolean canSum(int[] values, int count). Accept only a non-null array with 0 <= count <= values.length and count <= 64. Empty arrays with count 0 are valid.
Implement static long sumPrefix(int[] values, int count) under that precondition. Return 0 when count is 0 before any element access. Otherwise combine values[count - 1] with the result for count - 1.
Implement static long sumPrefixLoop(int[] values, int count) with the same precondition. Sum exactly the first count entries into a long local accumulator.
Neither calculation may print, modify elements, copy a smaller array on every step, or use a shared field accumulator. The recursive method must actually use its smaller call's result.
In main reject invalid input before either calculation, printing Use a non-null array and a count from 0 to min(length, 64). and returning without a normal report.
For valid data print Count:, Recursive total:, Loop total:, Repeated total:, and Input unchanged: in that order. Save an array snapshot before calculations and compare contents afterward. Repeated calls must be independent.

The starter supplies 12, -5, 20, and 7 with count 3. Only the first three entries belong to the requested prefix. No standard input is needed. Expected output:

Count: 3
Recursive total: 27
Loop total: 27
Repeated total: 27
Input unchanged: true

JAVA 21 COMPILER

Main.java · Build your bounded prefix sums

Predict the result, edit Main.java, then run your program.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        // TODO: validate, preserve an input snapshot, and compare both methods.
        // TODO: print the repeated-call and unchanged-input checks.
    }

    // TODO: declare canSum, sumPrefix, and sumPrefixLoop outside main.
    // Keep the recursive base check before any array indexing.
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        // TODO: validate, preserve an input snapshot, and compare both methods.
        // TODO: print the repeated-call and unchanged-input checks.
    }

    // TODO: declare canSum, sumPrefix, and sumPrefixLoop outside main.
    // Keep the recursive base check before any array indexing.
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Hints before the solution

Guard null before reading length. Check count against zero, length, and the exercise limit of 64. In the recursive helper, return zero immediately for count zero; otherwise include the element at count - 1 and the result for count - 1.

The loop uses index < count, not the full array length. Use long for both totals, keep all printing in main, and compare the final array with an independent snapshot. A single shared accumulator would defeat the repeated-call check.

Reveal the explained lab solution

JAVA 21 COMPILER

Main.java · Recursive and iterative prefix solution

Predict the result, edit Main.java, then run your program.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        if (!canSum(values, count)) {
            System.out.println("Use a non-null array and a count from 0 to min(length, 64).");
            return;
        }
        int[] before = Arrays.copyOf(values, values.length);
        long recursive = sumPrefix(values, count);
        long iterative = sumPrefixLoop(values, count);
        long repeated = sumPrefix(values, count);
        System.out.println("Count: " + count);
        System.out.println("Recursive total: " + recursive);
        System.out.println("Loop total: " + iterative);
        System.out.println("Repeated total: " + repeated);
        System.out.println("Input unchanged: " + Arrays.equals(values, before));
    }

    static boolean canSum(int[] values, int count) {
        return values != null && count >= 0 && count <= values.length && count <= 64;
    }

    // Precondition: canSum(values, count) is true. Reads without mutation.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }

    // Same precondition. Iterative reference implementation.
    static long sumPrefixLoop(int[] values, int count) {
        long total = 0;
        for (int index = 0; index < count; index++) {
            total += values[index];
        }
        return total;
    }
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        if (!canSum(values, count)) {
            System.out.println("Use a non-null array and a count from 0 to min(length, 64).");
            return;
        }
        int[] before = Arrays.copyOf(values, values.length);
        long recursive = sumPrefix(values, count);
        long iterative = sumPrefixLoop(values, count);
        long repeated = sumPrefix(values, count);
        System.out.println("Count: " + count);
        System.out.println("Recursive total: " + recursive);
        System.out.println("Loop total: " + iterative);
        System.out.println("Repeated total: " + repeated);
        System.out.println("Input unchanged: " + Arrays.equals(values, before));
    }

    static boolean canSum(int[] values, int count) {
        return values != null && count >= 0 && count <= values.length && count <= 64;
    }

    // Precondition: canSum(values, count) is true. Reads without mutation.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }

    // Same precondition. Iterative reference implementation.
    static long sumPrefixLoop(int[] values, int count) {
        long total = 0;
        for (int index = 0; index < count; index++) {
            total += values[index];
        }
        return total;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

The first three entries sum to 12 - 5 + 20 = 27; the trailing 7 is excluded. count moves through 3, 2, 1, and 0, while each invocation waits to combine its own included element with the smaller result. The same array is read throughout, and each count is a copied primitive parameter. main validates the depth and index bounds before calling either implementation. The loop supplies an independent reference result, and the repeated call plus snapshot check guard against shared accumulation and accidental mutation. The 64-element limit is a deliberately small teaching contract, not a JVM-wide recursion guarantee.

Test changes and boundaries

Edit values and count in the source. Reset restores the original program. Check zero, one, and several included elements before trying the stated upper bound; rejected inputs must not enter either calculation.

Use count 3 with the supplied data for 27, then count 4 for 34. Both implementations and the repeated call must agree without changing input.
Use an empty array with count 0, then a nonempty array with count 0. Every total must be zero, with no element access in the recursive base case.
Test count 1 with a single negative value such as -8. Expect -8, proving the progress rule depends on count rather than the sign of an element.
Reject null, a negative count, a count beyond the array length, and count 65 even when the array is long enough. Do not invoke the recursive helper for these cases.
Try two Integer.MAX_VALUE entries with count 2 for 4294967294. Also compare both implementations over all prefixes of a small test array and verify the largest permitted count of 64 using a small generated array.

Common mistakes and how to diagnose them

The base case exists but is never reached

Check the accepted input domain and the direction of each recursive argument change. n - 1 from a negative starting value does not approach a zero base as intended. Validate first and trace a few steps without running unbounded recursion.

The calls finish but the final answer is too small

A smaller return value may be discarded. A correct combination such as n + sumTo(n - 1) uses it; calling sumTo(n - 1) as a separate statement and then returning n does not.

The output appears in reverse order

Inspect whether printing is before or after the recursive call. Work after the call waits for deeper invocations and therefore happens as calls return. Predict entry order separately from return order.

Factorial returns zero or an overflowed number

Use the operation's correct base value: factorial(0) is 1. Also enforce the numeric range. A long return type handles factorial only through 20 here, not arbitrary positive n.

An empty prefix throws an index error

Check count == 0 before reading values[count - 1]. Validate count against array length first. A base result should require no access to a nonexistent element.

StackOverflowError or resource-limit termination

The algorithm may recurse without progress or simply require too much depth. Use bounded inputs or an iterative design rather than treating errors as termination. A tail-position call is not a portable Java 21 promise of constant stack use.

Frequently asked questions

Does return from the base case end every recursive call?

No. It finishes that invocation and resumes its caller. Earlier invocations can then do their pending work and return their own results, one at a time.

Does recursion share one local n between calls?

No. Each invocation has its own parameter and local working values. A shared array reference or a field can still expose shared objects or state, but that is separate from the recursive parameter copies.

Is recursion always slower than a loop?

There is no universal rule for every algorithm and runtime. In the linear examples here, recursion adds growing call-stack depth without changing the required additions. Choose a loop when it states a long simple traversal more directly.

Is a base case enough to prove safety?

No. Permitted inputs must reach it, arithmetic must stay within range, and the required stack depth and total work must be acceptable. Each of those is a separate check.

Why does the lab limit count to 64?

It keeps this teaching exercise small and bounded. It is not a universal safe recursion depth or a maximum imposed by Java. Runtime stack capacity depends on the method and configuration.

Explain the base, the progress, and the combination

Recursion uses ordinary method calls on smaller tasks. Each invocation keeps its own working values, and returning from the base resumes waiting callers. Correctness needs the right base result, reachable progress, and a meaningful use of the smaller returned result.

Before moving on, explain why factorial does not use zero as its base result, why a valid empty prefix needs no array access, and why a terminating algorithm can still exhaust resources. Next: the Methods Challenge, where you will combine method contracts and validation in a price calculator.

References and related learning

The scenarios, explanations, examples, and exercises are original SovranCode material. Official references support the Java 21 invocation and resource rules.

Review independent invocation state · Review returned results · Review iterative traversal · Java course roadmap.

Last updated: 21 October 2026

Java foundations · Lesson 21 About 60 min with practice

Java Recursion

Solve a small task by solving a smaller version of it. Trace the base case, the pending calls, and the results coming back—then decide when a loop is the clearer and safer choice.

What you will be able to do

Identify the base case and explain why recursive calls eventually reach it.
Trace work before a recursive call separately from work after it returns.
Keep each invocation's parameters and local results distinct.
Combine a smaller subproblem's result instead of discarding it.
Distinguish termination, numeric range, stack depth, and repeated-work costs.
Implement and test a bounded recursive calculation against a loop without mutating input.

A recursive method calls itself on a smaller task

JAVA 21 COMPILER

Main.java · Do work before the smaller call

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        countDown(3);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        countDown(3);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

3
2
1
Done.

Work before and after the call happens in different orders

JAVA 21 COMPILER

Main.java · Do work after the smaller call returns

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        countUp(3);
        System.out.println("Back in main.");
    }

    // Precondition: n is between 0 and 20.
    static void countUp(int n) {
        if (n == 0) {
            return;
        }
        countUp(n - 1);
        System.out.println(n);
    }
}

public class Main {
    public static void main(String[] args) {
        countUp(3);
        System.out.println("Back in main.");
    }

    // Precondition: n is between 0 and 20.
    static void countUp(int n) {
        if (n == 0) {
            return;
        }
        countUp(n - 1);
        System.out.println(n);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

1
2
3
Back in main.

Each invocation keeps its own parameters and pending result

JAVA 21 COMPILER

Main.java · Trace parameters going down and results coming back

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Total: " + sumTo(3));
    }

    // Precondition: n is between 0 and 20. Trace output is intentional here.
    static int sumTo(int n) {
        System.out.println("Enter: " + n);
        if (n == 0) {
            System.out.println("Base returns: 0");
            return 0;
        }
        int smaller = sumTo(n - 1);
        int result = n + smaller;
        System.out.println("Return from " + n + ": " + result);
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Total: " + sumTo(3));
    }

    // Precondition: n is between 0 and 20. Trace output is intentional here.
    static int sumTo(int n) {
        System.out.println("Enter: " + n);
        if (n == 0) {
            System.out.println("Base returns: 0");
            return 0;
        }
        int smaller = sumTo(n - 1);
        int result = n + smaller;
        System.out.println("Return from " + n + ": " + result);
        return result;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Enter: 3
Enter: 2
Enter: 1
Enter: 0
Base returns: 0
Return from 1: 1
Return from 2: 3
Return from 3: 6
Total: 6

Explain sumTo(3), one returning call at a time

sumTo(3) waits for sumTo(2).
sumTo(2) waits for sumTo(1), which waits for sumTo(0).
sumTo(0) returns the base result 0.
The n = 1 call returns 1 + 0 = 1.
The n = 2 call returns 2 + 1 = 3.
The n = 3 call returns 3 + 3 = 6 to main.

The two threes in the final addition have different roles: the current input is 3, and the smaller returned sum is also 3.

A base case is not a substitute for an input contract

JAVA 21 COMPILER

Main.java · Reject invalid input before recursion

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        int n = -1;
        if (n < 0 || n > 20) {
            System.out.println("Choose an integer from 0 through 20.");
            return;
        }
        countDown(n);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int n = -1;
        if (n < 0 || n > 20) {
            System.out.println("Choose an integer from 0 through 20.");
            return;
        }
        countDown(n);
    }

    // Precondition for this exercise: n is between 0 and 20.
    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Done.");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Choose an integer from 0 through 20.

Test zero, one, and rejected input safely

Change n to 0: only Done. should print. Change it to 1: expect 1, then Done. Keep the guard when trying -1 or 21: each must print only the validation message rather than enter recursion.

The base result must fit the calculation

JAVA 21 COMPILER

Main.java · A valid base result depends on the operation

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        int n = 5;
        if (n < 0 || n > 20) {
            System.out.println("Factorial input must be 0..20.");
            return;
        }
        System.out.println(n + "! = " + factorial(n));
    }

    // Precondition: 0 <= n <= 20, so the result fits in long.
    static long factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int n = 5;
        if (n < 0 || n > 20) {
            System.out.println("Factorial input must be 0..20.");
            return;
        }
        System.out.println(n + "! = " + factorial(n));
    }

    // Precondition: 0 <= n <= 20, so the result fits in long.
    static long factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

5! = 120

A smaller subproblem does not always mean subtracting one

JAVA 21 COMPILER

Main.java · Reduce a nonnegative number by removing a digit

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Digit sum: " + digitSum(507));
        System.out.println("Zero digit sum: " + digitSum(0));
    }

    // Precondition: value is a nonnegative int.
    static int digitSum(int value) {
        if (value < 10) {
            return value;
        }
        return value % 10 + digitSum(value / 10);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Digit sum: " + digitSum(507));
        System.out.println("Zero digit sum: " + digitSum(0));
    }

    // Precondition: value is a nonnegative int.
    static int digitSum(int value) {
        if (value < 10) {
            return value;
        }
        return value % 10 + digitSum(value / 10);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Digit sum: 12
Zero digit sum: 0

Use a count to shrink the task without changing the data

JAVA 21 COMPILER

Main.java · Describe a smaller array prefix without copying it

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        int[] values = {4, -2, 7};
        System.out.println("Prefix total: " + sumPrefix(values, 3));
        System.out.println("Empty prefix: " + sumPrefix(values, 0));
    }

    // Preconditions: non-null values, 0 <= count <= values.length, count <= 64.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int[] values = {4, -2, 7};
        System.out.println("Prefix total: " + sumPrefix(values, 3));
        System.out.println("Empty prefix: " + sumPrefix(values, 0));
    }

    // Preconditions: non-null values, 0 <= count <= values.length, count <= 64.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Prefix total: 9
Empty prefix: 0

Which element belongs to count 3?

A loop can compute the same result with less call-stack depth

JAVA 21 COMPILER

Main.java · Compare recursive and iterative sums

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Recursive: " + sumTo(5));
        System.out.println("Loop: " + sumToLoop(5));
    }

    // Precondition for both methods: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }

    static int sumToLoop(int n) {
        int total = 0;
        for (int value = 1; value <= n; value++) {
            total += value;
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Recursive: " + sumTo(5));
        System.out.println("Loop: " + sumToLoop(5));
    }

    // Precondition for both methods: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }

    static int sumToLoop(int n) {
        int total = 0;
        for (int value = 1; value <= n; value++) {
            total += value;
        }
        return total;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

Recursive: 15
Loop: 15

Several recursive calls can repeat the same subproblem

JAVA 21 COMPILER

Main.java · Two smaller calls can repeat the same work

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("fib(5): " + fibonacci(5));
    }

    // Small teaching input only: 0 <= n <= 10. This is not an efficient implementation.
    static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("fib(5): " + fibonacci(5));
    }

    // Small teaching input only: 0 <= n <= 10. This is not an efficient implementation.
    static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output · trace calls going down separately from results coming back

fib(5): 5

Find a repeated subproblem without increasing the input

Correct termination does not guarantee unlimited safe depth

Repair exercise: keep the smaller returned result

This bounded recursive sum reaches zero but discards every smaller result. It returns 3 instead of 6 for input 3. Repair the combination step, keeping the zero base case and the decreasing argument.

JAVA 21 COMPILER

Main.java · Repair a lost smaller sum

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        sumTo(n - 1);
        return n;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        sumTo(n - 1);
        return n;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Reveal the explained repair

JAVA 21 COMPILER

Main.java · Repaired recursive combination

Predict the result, edit Main.java, then run your program.

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Sum: " + sumTo(3));
    }

    // Precondition for this exercise: 0 <= n <= 20.
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n - 1);
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Expected output

Sum: 6

Independent lab: sum a bounded prefix two ways

Implement static boolean canSum(int[] values, int count). Accept only a non-null array with 0 <= count <= values.length and count <= 64. Empty arrays with count 0 are valid.
Implement static long sumPrefix(int[] values, int count) under that precondition. Return 0 when count is 0 before any element access. Otherwise combine values[count - 1] with the result for count - 1.
Implement static long sumPrefixLoop(int[] values, int count) with the same precondition. Sum exactly the first count entries into a long local accumulator.
Neither calculation may print, modify elements, copy a smaller array on every step, or use a shared field accumulator. The recursive method must actually use its smaller call's result.
In main reject invalid input before either calculation, printing Use a non-null array and a count from 0 to min(length, 64). and returning without a normal report.
For valid data print Count:, Recursive total:, Loop total:, Repeated total:, and Input unchanged: in that order. Save an array snapshot before calculations and compare contents afterward. Repeated calls must be independent.

The starter supplies 12, -5, 20, and 7 with count 3. Only the first three entries belong to the requested prefix. No standard input is needed. Expected output:

Count: 3
Recursive total: 27
Loop total: 27
Repeated total: 27
Input unchanged: true

JAVA 21 COMPILER

Main.java · Build your bounded prefix sums

Predict the result, edit Main.java, then run your program.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        // TODO: validate, preserve an input snapshot, and compare both methods.
        // TODO: print the repeated-call and unchanged-input checks.
    }

    // TODO: declare canSum, sumPrefix, and sumPrefixLoop outside main.
    // Keep the recursive base check before any array indexing.
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        // TODO: validate, preserve an input snapshot, and compare both methods.
        // TODO: print the repeated-call and unchanged-input checks.
    }

    // TODO: declare canSum, sumPrefix, and sumPrefixLoop outside main.
    // Keep the recursive base check before any array indexing.
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Hints before the solution

Reveal the explained lab solution

JAVA 21 COMPILER

Main.java · Recursive and iterative prefix solution

Predict the result, edit Main.java, then run your program.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        if (!canSum(values, count)) {
            System.out.println("Use a non-null array and a count from 0 to min(length, 64).");
            return;
        }
        int[] before = Arrays.copyOf(values, values.length);
        long recursive = sumPrefix(values, count);
        long iterative = sumPrefixLoop(values, count);
        long repeated = sumPrefix(values, count);
        System.out.println("Count: " + count);
        System.out.println("Recursive total: " + recursive);
        System.out.println("Loop total: " + iterative);
        System.out.println("Repeated total: " + repeated);
        System.out.println("Input unchanged: " + Arrays.equals(values, before));
    }

    static boolean canSum(int[] values, int count) {
        return values != null && count >= 0 && count <= values.length && count <= 64;
    }

    // Precondition: canSum(values, count) is true. Reads without mutation.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }

    // Same precondition. Iterative reference implementation.
    static long sumPrefixLoop(int[] values, int count) {
        long total = 0;
        for (int index = 0; index < count; index++) {
            total += values[index];
        }
        return total;
    }
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] values = {12, -5, 20, 7};
        int count = 3;
        if (!canSum(values, count)) {
            System.out.println("Use a non-null array and a count from 0 to min(length, 64).");
            return;
        }
        int[] before = Arrays.copyOf(values, values.length);
        long recursive = sumPrefix(values, count);
        long iterative = sumPrefixLoop(values, count);
        long repeated = sumPrefix(values, count);
        System.out.println("Count: " + count);
        System.out.println("Recursive total: " + recursive);
        System.out.println("Loop total: " + iterative);
        System.out.println("Repeated total: " + repeated);
        System.out.println("Input unchanged: " + Arrays.equals(values, before));
    }

    static boolean canSum(int[] values, int count) {
        return values != null && count >= 0 && count <= values.length && count <= 64;
    }

    // Precondition: canSum(values, count) is true. Reads without mutation.
    static long sumPrefix(int[] values, int count) {
        if (count == 0) {
            return 0;
        }
        return (long) values[count - 1] + sumPrefix(values, count - 1);
    }

    // Same precondition. Iterative reference implementation.
    static long sumPrefixLoop(int[] values, int count) {
        long total = 0;
        for (int index = 0; index < count; index++) {
            total += values[index];
        }
        return total;
    }
}

Standard input · optional

TERMINAL OUTPUT

Select Run code to compile and execute this program.

Test changes and boundaries

Use count 3 with the supplied data for 27, then count 4 for 34. Both implementations and the repeated call must agree without changing input.
Use an empty array with count 0, then a nonempty array with count 0. Every total must be zero, with no element access in the recursive base case.
Test count 1 with a single negative value such as -8. Expect -8, proving the progress rule depends on count rather than the sign of an element.
Reject null, a negative count, a count beyond the array length, and count 65 even when the array is long enough. Do not invoke the recursive helper for these cases.
Try two Integer.MAX_VALUE entries with count 2 for 4294967294. Also compare both implementations over all prefixes of a small test array and verify the largest permitted count of 64 using a small generated array.

Common mistakes and how to diagnose them

The base case exists but is never reached

The calls finish but the final answer is too small

A smaller return value may be discarded. A correct combination such as n + sumTo(n - 1) uses it; calling sumTo(n - 1) as a separate statement and then returning n does not.

The output appears in reverse order

Factorial returns zero or an overflowed number

Use the operation's correct base value: factorial(0) is 1. Also enforce the numeric range. A long return type handles factorial only through 20 here, not arbitrary positive n.

An empty prefix throws an index error

Check count == 0 before reading values[count - 1]. Validate count against array length first. A base result should require no access to a nonexistent element.

StackOverflowError or resource-limit termination

Frequently asked questions

Does return from the base case end every recursive call?

No. It finishes that invocation and resumes its caller. Earlier invocations can then do their pending work and return their own results, one at a time.

Does recursion share one local n between calls?

Is recursion always slower than a loop?

Is a base case enough to prove safety?

No. Permitted inputs must reach it, arithmetic must stay within range, and the required stack depth and total work must be acceptable. Each of those is a separate check.

Why does the lab limit count to 64?

It keeps this teaching exercise small and bounded. It is not a universal safe recursion depth or a maximum imposed by Java. Runtime stack capacity depends on the method and configuration.

Explain the base, the progress, and the combination

References and related learning

The scenarios, explanations, examples, and exercises are original SovranCode material. Official references support the Java 21 invocation and resource rules.

Review independent invocation state · Review returned results · Review iterative traversal · Java course roadmap.

Last updated: 21 October 2026

Java introduction and setup

Variables, values, and input

Conditions, loops, and arrays

Methods and problem solving

Classes, objects, and encapsulation

Inheritance and reusable object design

Errors, exceptions, and files

Collections and data structures

Practical advanced foundations

Java Recursion

What you will be able to do

A recursive method calls itself on a smaller task

Work before and after the call happens in different orders

Each invocation keeps its own parameters and pending result

A base case is not a substitute for an input contract

The base result must fit the calculation

A smaller subproblem does not always mean subtracting one

Use a count to shrink the task without changing the data

A loop can compute the same result with less call-stack depth

Several recursive calls can repeat the same subproblem

Correct termination does not guarantee unlimited safe depth

Repair exercise: keep the smaller returned result

Independent lab: sum a bounded prefix two ways

Test changes and boundaries

Common mistakes and how to diagnose them

The base case exists but is never reached

The calls finish but the final answer is too small

The output appears in reverse order

Factorial returns zero or an overflowed number

An empty prefix throws an index error

StackOverflowError or resource-limit termination

Frequently asked questions

Explain the base, the progress, and the combination

References and related learning

Java introduction and setup

Variables, values, and input

Conditions, loops, and arrays

Methods and problem solving

Classes, objects, and encapsulation

Inheritance and reusable object design

Errors, exceptions, and files

Collections and data structures

Practical advanced foundations

Java Recursion

What you will be able to do

A recursive method calls itself on a smaller task

Work before and after the call happens in different orders

Each invocation keeps its own parameters and pending result

A base case is not a substitute for an input contract

The base result must fit the calculation

A smaller subproblem does not always mean subtracting one

Use a count to shrink the task without changing the data

A loop can compute the same result with less call-stack depth

Several recursive calls can repeat the same subproblem

Correct termination does not guarantee unlimited safe depth

Repair exercise: keep the smaller returned result

Independent lab: sum a bounded prefix two ways

Test changes and boundaries

Common mistakes and how to diagnose them

The base case exists but is never reached

The calls finish but the final answer is too small

The output appears in reverse order

Factorial returns zero or an overflowed number

An empty prefix throws an index error

StackOverflowError or resource-limit termination

Frequently asked questions

Explain the base, the progress, and the combination

References and related learning