Recursion

Problem

How many arrangements are there?

There are 5 books on the shelf. In how many ways can you arrange them? For the first spot there are 5 choices, for the second 4, then 3, 2 and 1: 5 · 4 · 3 · 2 · 1 = 120. This is a factorial, written 5!.

You can already do it with a loop:

static int factorialLoop(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

System.out.println(factorialLoop(5));

Output

120

Look at it this way too: 5! = 5 · 4!. And 4! = 4 · 3!. The task is solved through the same task, only smaller. Can the method say exactly that?

The idea

A method that calls itself

It can. A method that calls itself is called recursive, and the approach is recursion.

static int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

System.out.println(factorial(5));

Output

120

Two things make it work:

• A base case. A case that is solved directly, without a new call. Here: 1! = 1.
• A smaller task. Each call calls itself with a number closer to the base case: n - 1.

See it

The pile of calls

static int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

System.out.println(factorial(3));  // 6

Step by step, in words

1. main calls factorial(3).
2. New memory for factorial with n = 3.
3. 3 is not 1, so the method calls factorial(2) and waits for the answer.
4. The same again: factorial(2) calls factorial(1). Each call has its own n.
5. n is 1: this is the base case. It returns 1 without calling again.
6. The answer comes back down: 2 * 1 = 2.
7. And again: 3 * 2 = 6.
8. factorial(3) returns 6 and main prints it.

Each call gets its own memory with its own n. They pile up one on top of the other and wait. This pile is called the call stack. When the base case returns 1, the answers go back down one by one and the pile comes apart.

Try it

Down and back up

What will the program print?

static void steps(int n) {
    if (n == 0) {
        return;
    }
    System.out.println("down " + n);
    steps(n - 1);
    System.out.println("up " + n);
}

steps(2);

Answer

down 2
down 1
up 1
up 2

down 2
up 2
down 1
up 1

down 2
down 1
up 2
up 1

Check

Try it

Find the bug

sumTo(4) should return 1 + 2 + 3 + 4 = 10. Instead, the program stops with StackOverflowError. Which line is the bug on?

Pick the line with the bug.

1static int sumTo(int n) {2 if (n == 1) {3 return 1;4 }5 return n + sumTo(n);6}

Check

The idea

Recursion or a loop?

You can write the factorial with a loop or with recursion. Here the loop is the better choice: it does not pile up memory for each call, and for 100,000 calls the stack will not be enough.

Recursion is natural where a thing contains smaller things of the same kind: a folder with folders inside, a category with subcategories, a branch with branches. You will come across tasks like these later in the course. There a loop gets clumsy, while the recursive method stays short.

More precisely, if you are curious

• The factorial is often written with the base case 0! = 1 (if (n == 0)). Then it works for 0 too.

• An int is enough up to 12!. For 13! the result does not fit and the number comes out wrong. For bigger values, use long.

Try it

Put the lines in order

The method has to work out a power: power(2, 10) is 1024. Put its lines in order.

1. return 1;↑↓
2. }↑↓
3. return base * power(base, exp - 1);↑↓
4. if (exp == 0) {↑↓
5. static int power(int base, int exp) {↑↓
6. }↑↓

Check

Exercise

Recursive tasks

1. Factorial two ways. Write factorialLoop(int n) with a for loop and factorial(int n) with recursion. Read a number and print the result from both methods.

Input

5

Output

The factorial of 5 is 120
The factorial of 5 is 120

2. Sum of digits. sumDigits(int n): the last digit (n % 10) plus the sum of the digits of the rest (n / 10). The base case is a single-digit number.

3. Fibonacci. Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8… fib(int n) returns the nth number. Try it with 10, and then with 45. Why is it so slow? Hint: how many times is each number worked out?

4. Palindrome. isPalindrome(String s): the first and last letters are the same, and the middle is a palindrome. The base case is a word with 0 or 1 letters.

Calls

sumDigits(2024)
fib(10)
isPalindrome("level")
isPalindrome("ABCDE")

Output

8
55
true
false

Test

Check yourself

1. What is recursion?

Two methods with the same nameA loop inside a methodA method that calls itself

2. Why does a recursive method need a base case?

So it runs fasterSo it stops calling itselfSo it can return a result

3. factorial(3) calls factorial(2), and that calls factorial(1). How many variables n are in memory just before factorial(1) returns?

ThreeOneNone

4. What happens if the base case is never reached?

The method returns 0The program runs forever, with no errorThe stack overflows and the program stops with an error

Check

Start the lesson over