Java, lesson 11
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.
Every recursive method needs two parts:
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.
12624Each 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:
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.
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.
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);
}98765Digit sum: 35
Digital root: 82Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Total moves: 3