Recursion

A bouncing ball

A ball dropped from 100 centimeters bounces back to three fifths of its height each time. The method below counts how many heights in that sequence, the drop included, are at least 10 centimeters, using integer division.

public static int highPoints(int height)
{
    if (height < 10)
    {
        return 0;
    }
    return 1 + highPoints(height * 3 / 5);
}

The first return is the base case: a height under 10 gets an answer with no further call. The second contains the recursive call, on a smaller height. Each call's height is smaller than its caller's, so the heights eventually drop below 10 and the calls stop.

Tracing the calls

highPoints(100) can't return until highPoints(60) does, and that one depends on highPoints(36). The calls go on through 21, 12, and 7. The call with 7 reaches the base case and returns 0. Then each pending call adds 1 to its result, from the innermost outward. So the calls with 12, 21, 36, 60, and 100 return 1, 2, 3, 4, and 5.

While highPoints(7) runs, five other calls are unfinished, and each still holds its own height. The call with 60 can't change the 100 held by its caller.

Output before and after the call

public static void heights(int height)
{
    if (height >= 10)
    {
        System.out.print(height + " ");
        heights(height * 3 / 5);
        System.out.print(height + " ");
    }
}

heights(100) prints 100 60 36 21 12 12 21 36 60 100. Each call's first print happens before it calls again, so the first five numbers appear from the outermost call inward. Its second print waits until every call below it has finished, so the last five appear from the innermost call outward.

The same work with a loop

This loop counts the same heights.

int count = 0;
while (height >= 10)
{
    count++;
    height = height * 3 / 5;
}

Where the recursive version passes a smaller height to a new call, the loop assigns the smaller height to the same variable. Both stop at the same condition, so for 100 both give 5.