Learn/Java/11. Recursion
Lesson 11 of 15
Sign in

Java, lesson 11

Recursion

A recursive method is one that calls itself. That sounds like a recipe for an endless loop, but it is a powerful way to think: solve a big problem by solving a smaller copy of the same problem, and stop when the problem is so small that the answer is obvious.

Base case and recursive case

Every recursive method needs two parts:

  1. A base case: an input small enough to answer directly, without recursion.
  2. A recursive case: the method calls itself with an input that is closer to the base case, then uses that result.

The classic example is factorial, n! = n × (n-1) × … × 1:

factorial(4) asks for 4 * factorial(3), which asks for 3 * factorial(2), then 2 * factorial(1), which is the base case and returns . The answers then flow back up: , , .

2 exercises to try what you just read.

Exercise 1

Digital root

Press Ctrl Enter or Check to test your code.

Exercise 2

Tower of Hanoi

Press Ctrl Enter or Check to test your code.

1
2
6
24

The call stack

Each call gets its own copy of the parameters and local variables, kept in a stack frame. The frames pile up until the base case is reached, then unwind one by one. The stack has a limited size. If the recursion never reaches a base case, or simply goes too deep (tens of thousands of levels), Java throws a StackOverflowError. So:

  • Make sure every recursive call moves toward the base case.
  • For a simple count-down over a huge range, a loop is the better tool.

Thinking recursively

The trick is to trust the recursive call. When writing sumDigits(n), assume sumDigits(n / 10) already works for the smaller number, and ask only: "how do I use that answer to finish the job?"

Recursion is natural for problems that have the same shape at every size: nested folders, family trees, mathematical definitions, splitting a list in halves, or exploring every move in a puzzle.

When recursion gets slow

A method that makes two recursive calls can explode. The naive Fibonacci fib(n) = fib(n-1) + fib(n-2) recomputes the same values again and again, so fib(50) would take ages. The fix is memoization: remember answers you have already computed, for example in a HashMap<Integer, Long> or an array, and look them up before recursing.

Further reading

  • Defining methods (dev.java)
  • StackOverflowError API

Write a recursive method static int digitSum(long n) that returns the sum of the digits of a non-negative number. Then write a recursive static int digitalRoot(long n): if n has one digit, it is the answer; otherwise the answer is the digital root of its digit sum.

Read one non-negative whole number (it can be as large as a long) and print both values.

Sample input:

Sample output:

You have three pegs, A, B and C, and n disks stacked on A, largest at the bottom. Move them all to C, one disk at a time, never putting a bigger disk on a smaller one.

The recursive idea: to move n disks from A to C, first move n - 1 disks from A to B (using C as the spare), then move disk n from A to C, then move the n - 1 disks from B to C (using A as the spare). Moving zero disks does nothing.

Read n (0 to 10) and print every move as Move disk <d> from <from> to <to>, then Total moves: <count>.

Sample input:

Sample output:

static long factorial(int n) {
    if (n <= 1) {
        return 1;                    // base case
    }
    return n * factorial(n - 1);     // recursive case: a smaller problem
}
static int sumDigits(long n) {
    if (n < 10) return (int) n;                  // one digit: it is its own sum
    return (int) (n % 10) + sumDigits(n / 10);   // last digit + sum of the rest
}
static String reverse(String s) {
    if (s.isEmpty()) return "";
    return reverse(s.substring(1)) + s.charAt(0);
}
98765
Digit sum: 35
Digital root: 8
2
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Total moves: 3