CS 4: Lecture 17 Monday, March 20, 2006 Recursion --------- _Recursion_ is the word for when a method calls itself. Recursion is a natural way to compute a factorial, for example. The factorial of a nonnegative integer n can be defined inductively as / | 1 , n = 0 or n = 1 n! = < | n (n - 1)! , n > 1 \ We can write recursive code that echoes this inductive definition. public static int factorial(long n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); } } If you call "factorial(0)" or "factorial(1)", the factorial method follows the first branch of the "if" statement, and simply returns 1. But suppose you call "factorial(4)". The factorial method computes 4! by calling "factorial(3)", multiplying 3! by 4, and returning the product. Seems odd, doesn't it? How can you depend on "factorial(3)" working when we're in the middle of writing the "factorial" code? The answer is because computing 3! is easier (takes less computation) than computing 4!. It's a lot like inductive proofs in mathematics. Recall how induction works. n Theorem: For all n >= 1, n! <= n . Proof: By induction. n Base case: Suppose n = 1. Then n! = 1 and n = 1, so the theorem holds for n = 1. Inductive step: Suppose n = j > 1. For the sake of induction, assume the theorem holds for all n _less_ than j. We'll show that it holds for n = j too. j - 1 j - 1 The theorem holds for n = j - 1, so (j - 1)! <= (j - 1) < j . j Multiplying both sides by j gives j! <= j . Therefore, the theorem holds for n = j. QED The recursive factorial method is a lot like this proof. - First, the recursive method has a _base_case_, which handles the cases n = 0 and n = 1. - Second, the recursive method _assumes_ that it itself works correctly for numbers less than n, and uses that fact to compute n!. The best way to understand recursion, though, is to think of what's happening on the stack. When you call "factorial(4)", a stack frame is created for the factorial method, with the local variable n set to 4. Then factorial makes the method call "factorial(3)". This puts a second stack frame for factorial on top of the stack, with the local variable n set to 3. Then factorial(3) calls factorial(2) which calls factorial(1), so we have four frames on the stack. method call parameters & local variables ----------------------------------------------| ----- | factorial n | 1 | | <- this is the base case ----- | ----------------------------------------------| ----- | factorial n | 2 | | ----- | ----------------------------------------------| ----- | factorial n | 3 | | ----- | ----------------------------------------------| ----- | factorial n | 4 | | ----- | ----------------------------------------------| ----- | main args | ? | | ----- | ----------------------------------------------| Finally, we've reached the base case; "factorial(1)" returns 1, and does not call "factorial" again. Then, "factorial(2)" multiplies 2 by 1 and returns 2. Then, "factorial(3)" multiplies 3 by 2 and returns 6. Finally, "factorial(4)" multiplies 4 by 6 and returns 24. The idea of scope is very important with recursion, because there could be hundreds of "factorial" stack frames on the stack at once, and thus hundreds of variables named "n". As always, _only_ the top stack frame is accessible at any given moment. The variable "n" in the factorial method always refers to the n in the top stack frame. What would happen if we wrote "factorial" like this? public static int factorial(long n) { return n * factorial(n - 1); } This "factorial" would keep calling itself forever--effectively, in an infinite loop--endlessly putting more stack frames on the stack, until the computer runs out of stack space and Java terminates with an error message. For recursion to work, you need to make sure that any call to a recursive method will always reach the base case eventually and stop calling itself. Most loops can be turned into recursive methods. For example, the following two methods print all the numbers from 1 to n. public static void count(long n) { | public static void count(long n) { for (long i = 1; i <= n; i++) { | if (n > 0) { System.out.println(i); | // Print numbers 1...n - 1 } | count(n - 1); } | System.out.println(n); | } | } How does the recursive version on the right work? It calls itself recursively to print all the numbers from 1...n - 1, then it prints n. The base case is n <= 0, for which the "count" method does nothing. What happens if we switch the order of the "println" call and the recursive call? public static void countDown(long n) { if (n > 0) { System.out.println(n); // Print numbers 1...n - 1 countDown(n - 1); } } This procedure prints n _first_, _then_ prints the numbers between 1 and n - 1. The effect is that it prints the numbers in reverse order, from n down to 1. Rewriting a simple loop (or even the factorial computation) as a recursive call isn't useful in practice, because the code just got longer and slower. However, some loops lend themselves naturally to a recursive expression. Here's a recursive version of the gcd method. static private long gcd(long a, long b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } The base case occurs when b = 0, because GCD(a, 0) = a. In all other cases, "gcd" calls itself recursively using the formula GCD(a, b) = GCD(b, r) we derived last week, where r is the remainder from dividing a by b. If you call gcd(15, 6), after two recursive calls the stack looks like this. method call parameters & local variables ----------------------------------------------| ----- ----- | gcd a | 3 | b | 0 | | <- this is the base case ----- ----- | ----------------------------------------------| ----- ----- | gcd a | 6 | b | 3 | | ----- ----- | ----------------------------------------------| ----- ----- | gcd a | 15| b | 6 | | ----- ----- | ----------------------------------------------| The top "gcd" on the stack has reached the base case; next, all the "gcd" methods on the stack (from top to bottom) will return 3. Here's an example of recursion from a computer game called "Dungeon of the Overlord" I wrote as a teen. It included a magic "Wand of Wonder". When you wave the magic wand, it casts a magic spell chosen randomly from a selected subset of all the possible magic spells. private magicSpell(int spellNumber) { // Make magic sound, other preparations.... switch(spellNumber) { ... case 38: // Wand of wonder. int randomSpell = (int) (15 * random.nextDouble()); // Spells 0...14 magicSpell(randomSpell); break; case 39: ... } }