Step 4 of 6

When recursion goes wrong

A recursive method needs a base case, and every call must get closer to it. When one of the two is missing, the calls never stop, and the program crashes.

No base case

Here is digits from step 2 with its base case left out. A program that crashes this way prints a very long report, so this one catches the error (module 42) and prints one line instead:

public class Main {
    public static void main(String[] args) {
        try {
            System.out.println(digits(4096));
        } catch (StackOverflowError e) {
            System.out.println("The calls never stopped: " + e);
        }
    }

    public static int digits(int n) {
        return 1 + digits(n / 10);
    }
}

Output

The calls never stopped: java.lang.StackOverflowError

digits(4096) calls digits(409), digits(40), digits(4) and digits(0), and then digits(0) again and again, since 0 / 10 is 0. None of the calls ever returns. Every call of a method takes some memory on the call stack for its parameters and variables, and gives it back when it returns. The call stack has a fixed size, so a chain of calls that never returns fills it up. Java then throws a StackOverflowError. It's an error, not an exception (its class extends Error, not Exception): errors are for problems a program usually can't recover from, and catching one is rare. It's done here only to keep the page short.

Without the try (with System.out.println(digits(4096)); alone in main), the program would crash with a report like this, where line 7 is the line of the recursive call:

Exception in thread "main" java.lang.StackOverflowError
	at Main.digits(Main.java:7)
	at Main.digits(Main.java:7)
	at Main.digits(Main.java:7)

and so on: the reference JDK prints 1,024 at lines, all of them the same. The report lists the calls that were on the stack, newest first, and a report whose at lines repeat one method is the sign of a recursion that doesn't stop.

The fix is the base case that was left out: a number below 10 has one digit, and the method returns 1 without calling itself.

A base case that's never reached

The quiz show's countDown from step 1 has a base case, seconds == 0:

public static void countDown(int seconds) {
    if (seconds == 0) {
        return;
    }
    System.out.println(seconds);
    countDown(seconds - 1);
}

countDown(3) prints 3, 2 and 1, and stops. But countDown(-3) prints -3, -4, -5... and never reaches 0, so it overflows the stack too. (On the reference JDK it prints thousands of lines first. Java Arena stops a program once it has printed 64 KB, so here a program like this is stopped for printing too much before the stack runs out.) The base case exists, but some inputs miss it. A base case written as a range, seconds <= 0, catches every input at or past the end. So when you write a recursive method, try it on the smallest inputs: 0, 1, a negative number, and odd and even numbers when the method takes steps of 2.

Calls that repeat work

A method can also call itself correctly and still be far too slow. A child climbs a staircase one or two steps at a time. In how many ways can they climb n steps? The first move is one step (then n - 1 steps are left) or two steps (then n - 2 are left), so the ways for n are the ways for n - 1 plus the ways for n - 2. 0 or 1 steps can be climbed in one way. These are the Fibonacci numbers.

public class Main {
    public static void main(String[] args) {
        System.out.println(ways(4));
        System.out.println(ways(30));
    }

    public static long ways(int steps) {
        if (steps <= 1) {
            return 1;
        }
        return ways(steps - 1) + ways(steps - 2);
    }
}

Output

5
1346269

The answer is right, but each call makes two more, and they repeat the same work: ways(30) calls ways(29) and ways(28), and ways(29) calls ways(28) again. The number of calls grows about as fast as the answer itself; for ways(30), it's over two million, and every 10 more steps make it more than a hundred times larger. A loop that adds up the ways from the bottom (or a recursive method that remembers its answers in a HashMap) does about one round per step. The third challenge of this step counts the calls.

Your task

Challenge 1 of 3

A ball is dropped from a height in centimeters, and each bounce reaches half the height of the one before, in whole centimeters (/ 2 on an int). From 40 it reaches 40, 20, 10, 5, 2 and 1, and then it lies still. heights(height) should return how many of those heights are above 0, the first drop included: 6 for 40. The method below has no base case: after 1 it calls heights(0), and heights(0) calls heights(0) again and again (0 / 2 is 0), until the StackOverflowError. Add a base case: for a height of 0 there is nothing left to count, so it returns 0 without calling itself. Keep the method recursive. The check runs System.out.println(heights(40)); and expects:

Challenge 2

A staircase is climbed two steps at a time; when one step is left, the last move is a single step. moves(steps) should return how many moves the climb takes: 3 for 6 steps, 3 for 5 steps (2 + 2 + 1), and 0 for 0 steps or fewer. The method below works for even numbers, but an odd number jumps over its base case, and so does a negative one, and the program crashes with a StackOverflowError. Fix the base case so that every input reaches it. Keep the method recursive. The check runs:

System.out.println(moves(6));
System.out.println(moves(5));
System.out.println(moves(-4));

and expects:

3
3
0

Challenge 3

How much work does ways repeat? The program reads a number of steps, n, and prints the number of ways to climb them (the method of this step), then how many times ways was called in all, the first call included. Count the calls in a variable that ways adds one to each time it starts. A variable declared inside ways won't do, since each call gets its own. Declare it in the class, outside the methods, with static: private static long calls = 0;. A static variable belongs to the class itself, not to an object or a call, so every call of ways and main see the same one.

For 4 steps, ways(4) calls ways(3) and ways(2); ways(3) calls ways(2) and ways(1); each ways(2) calls ways(1) and ways(0). That's 9 calls. With the input 20, the program prints:

Ways: 10946
Calls: 21891

Previous: Recursion on strings and arrays Next: Recursive binary search