Step 2 of 6

Base case and return value

The methods of step 1 printed something and returned nothing. A recursive method can also return a value, and that's where recursion gets useful: the method builds its answer from the answer to a smaller problem.

Counting digits

How many digits does a whole number have? A number below 10 has one digit. A larger number has one digit more than the number without its last digit, and n / 10 drops the last digit (module 4): 4096 has one digit more than 409.

public class Main {
    public static void main(String[] args) {
        System.out.println(digits(7));
        System.out.println(digits(4096));
    }

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

Output

1
4

Read the method as two sentences: "a number below 10 has 1 digit" and "any other number has 1 more digit than n / 10". The base case answers the smallest problem directly; the recursive case trusts the recursive call to give the right answer for the smaller problem, and adds its own part.

Following the calls

digits(4096) can't return until it knows digits(409), which waits for digits(40), which waits for digits(4). That one is a base case, and returns 1. Then the waiting calls finish, from the newest to the oldest, each adding 1 to what it got back:

digits(4096) = 1 + digits(409)
                   digits(409) = 1 + digits(40)
                                     digits(40) = 1 + digits(4)
                                                      digits(4) = 1
                                     digits(40) = 1 + 1 = 2
                   digits(409) = 1 + 2 = 3
digits(4096) = 1 + 3 = 4

Two questions check a recursive method:

Is every base case answered correctly, without a recursive call?
Does every other input get closer to a base case with each call? Here, dividing by 10 makes any number of 10 or more smaller, so the calls end up below 10.

If both are true, and the recursive case is right whenever the smaller call returns the right answer, the method is right for every input.

Where the base case comes from

Choose the smallest input for which the answer is obvious. For a sum of the numbers from 1 to n, that's n = 0: there's nothing to add, and the sum is 0. Picking 0 rather than 1 also makes the method work when it's called with 0.

Your task

Challenge 1 of 3

A grocer stacks oranges in a triangle: the bottom row has rows oranges, the row above it one fewer, and so on up to a single orange at the top. Write the method oranges(int rows), which returns how many oranges the stack has, with recursion and no loop. A stack of 0 rows has 0 oranges. The check runs:

System.out.println(oranges(4));
System.out.println(oranges(1));

and expects:

10
1

Challenge 2

A bookshop owner wants to know in how many different orders a number of books can stand on a shelf. One book stands in 1 order. With 2 books there are 2 orders, and with 3 books 6: any of the 3 can stand first, and the other 2 stand after it in 2 orders. In general, n books stand in n times as many orders as n - 1 books. That's the factorial of n, written n!. An empty shelf counts as 1 order (0! = 1).

The numbers grow fast, so write the method orders(int books) that returns a long, with recursion and no loop. A long holds factorials up to 20!. The check runs:

System.out.println(orders(3));
System.out.println(orders(0));
System.out.println(orders(15));

and expects:

6
1
1307674368000

Challenge 3

A sheet of paper doubles in thickness each time it's folded in half; a strip cut in three and stacked triples. Write the method power(int base, int exponent), which returns base multiplied by itself exponent times, as a long: power(2, 5) is 2 * 2 * 2 * 2 * 2, 32. Any number to the power of 0 is 1, and that's the base case. Use recursion, no loop and no Math.pow. The exponent is never negative. The check runs:

System.out.println(power(2, 5));
System.out.println(power(3, 4));
System.out.println(power(7, 0));

and expects:

32
81
1

Previous: A method that calls itself Next: Recursion on strings and arrays