1.1 Base Cases | Code Scholars Tutoring

How it works

A base case stops the recursion. It must be reachable from every possible call, which is a stronger requirement than merely existing.

Write the base case first, then check that each recursive call strictly reduces the input toward it.

Common error

A base case that exists but is unreachable for some inputs, such as testing equality when the input decreases by two.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

class Solver {
    int sum(int n) {
        if (n == 0) return 0;
        return n + sum(n - 1);
    }
}
System.out.println(new Solver().sum(4));

Output

The base case handles zero directly. Each recursive call reduces a nonnegative n, so the call chain eventually reaches zero and its results add back upward.

Exercises

1.1.1 · Explain

What goes wrong with sum(n) = n + sum(n - 1) if it has no base case?

Show solution

There is no stopping condition, so the computation continues making calls until the runtime cannot grow the call stack further.

1.1.2 · Write code

Write a recursive factorial for nonnegative n and show factorial(0) and factorial(5).

Show solution

Use 1 as the empty-product base result and decrease n.

One valid solution

class Solver {
    long fact(int n) {
        if (n == 0) return 1;
        return n * fact(n - 1);
    }
}
Solver s = new Solver();
System.out.println(s.fact(0));
System.out.println(s.fact(5));

Expected output

1
120

Open Java compiler