# Chapter 18. Recursion examples

When examining recursion in the previous chapter, we looked at several examples of recursion, but the problems were always just as easy to solve using loops. The chapter promised that eventually we would see examples where recursion could do things that can't easily be done otherwise. We'll see some examples now.

## 18.1. Fibonacci numbers

But let's start with an example that isn't particularly useful but which helps to illustrate a good way of illustrating recursion at work. We will build a recursive method to compute numbers in the Fibonacci sequence. This infinite sequence starts with 0 and 1, which we'll think of as the zeroth and first Fibonacci numbers, and each succeeding number is the sum of the two preceding Fibonacci numbers. Thus, the second number is 0 + 1 = 1. And to get the third Fibonacci number, we'd sum the first (1) and the second (1) to get 2. And the fourth is the sum of the second (1) and the third (2), which is 3. And so on.

 `n`: 0 1 2 3 4 5 6 7 8 9 10 11 … `n`th Fibonacci: 0 1 1 2 3 5 8 13 21 34 55 89 …

We want to write a method `fib` that takes some integer `n` as a parameter and returns the `n`th Fibonacci number, where we think of the first 1 as the first Fibonacci number. Thus, an invocation of `fib(6)` should return 8, and in invocation of `fib(7)` should return 13.

```public int fib(int n) {     if(n <= 1) {         return n;     } else {         return fib(n - 1) + fib(n - 2);     } } ```

In talking about recursive procedures such as this, it's useful to be able to diagram the various method calls performed. We'll do this using a recursion tree. The recursion tree for computing `fib(5)` is in Figure 18.1.

Figure 18.1: Recursion tree for computing `fib(5)`. The recursion tree has the original parameter (5 in this case) at the top, representing the original method invocation. In the case of `fib(5)`, there would be two recursive calls, to `fib(4)` and `fib(3)`, so we include 4 and 3 in our diagram below 5 and draw a line connecting them. Of course, `fib(4)` has two recursive calls itself, diagrammed in the recursion tree, as does `fib(3)`. The complete diagram in Figure 18.1 depicts all the recursive invocation of `fib` made in the course of computing `fib(5)`. The bottom of the recursion tree depicts those cases when there are no recursive calls — in this case, when `n <= 1`. Though Fibonacci computation is a classical example of recursion, it has a major shortcoming: It's not a compelling example. There are two reasons for this. First, how often do you expect to want to compute Fibonacci numbers? (The Fibonacci sequence admittedly appears in surprising circumstances, like the numbers of spirals on pine cones and sunflowers, but even those cases rarely require computing large Fibonacci numbers.) And second, the above recursive method isn't a good technique for doing it anyway. In fact, if you measure the speed by the number of additions performed, the recursive technique above will take `fib(n)` − 1 additions; to see this, you can take the above recursion tree and notice that the overall return value is computed as

(((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1) .

Essentially, we are summing `fib(n)` 1's, which will require `fib(n)` − 1 additions. A much faster way is to start with the first two Fibonaccis and to extend the sequence one by one, each time adding the previous two numbers, until we reach the `n`th Fibonacci. Computing each Fibonacci requires just one addition, so the total number of additions is `n` − 1, which is much less than `fib(n)` − 1 for large `n`.

## 18.2. Anagrams

Our first example is the problem of listing all the rearrangements of a word entered by the user. For example, if the user types east, the program should list all 24 permutations, including eats, etas, teas, and non-words like tsae. If we want the program to work with any length of word, there is no straightforward way of performing this task without recursion.

With recursion, though, we can do it by thinking through the magical assumption. If we had a four-letter word, our magical assumption allows us to presume our recursive method knows how to handle all words with fewer than four letters. So what we might hope to do is to take each letter of the four-letter word, and place that letter at the front of all the three-letter permutations of the remaining letters. Given east, we would place e in front of all six permutations of astast, ats, sat, sta, tas, and tsa — to arrive at east, eats, esat, esta, etas, and etsa. Then we would place a in front of all six permutations of est, then s in front of all six permutations of eat, and finally t in front of all six permutations of eas. Thus, there will be four recursive calls to display all permutations of a four-letter word.

Of course, when we're going through the anagrams of ast, we would follow the same procedure. We first display an a in front of each anagram of st, then an s in front of each anagram of at, and finally a t in front of each anagram of as. As we display each of these anagrams of ast, we want to display the letter e before it.

To translate this concept into Java code, our recursive method will need two parameters. The more obvious parameter will be the word whose anagrams to display, but we also need the letters that we want to print before each of those anagrams. At the top level of the recursion, we may want to print all anagrams of east, without printing any letters before each anagram. But in the next level, one recursive call will be to to display all anagrams of ast, prefixing each with the letter e. And in the next level below that, one recursive call will be to display all anagrams of st, prefixing each with the letters ea.

The base case of our recursion would be when we reach a word with just one letter. Then, we just display the prefix followed by the one letter in question.

This is the thought process that leads to the working implementation found in Figure 18.2.

Figure 18.2: The `Anagrams` program.

```  1  import acm.program.*;   2     3  public class Anagrams extends Program {   4      public void run() {   5          String word = readLine("Give a word to anagram: ");   6          printAnagrams("", word);   7      }   8     9      public void printAnagrams(String prefix, String word) {  10          if(word.length() <= 1) {  11              println(prefix + word);  12          } else {  13              for(int i = 0; i < word.length(); i++) {  14                  String cur = word.substring(i, i + 1);  15                  String before = word.substring(0, i); // letters before cur  16                  String after = word.substring(i + 1); // letters after cur  17                  printAnagrams(prefix + cur, before + after);  18              }  19          }  20      }  21  } ```

## 18.3. Sierpinski Carpet

Recursion can help in displaying complex patterns where the pattern appears inside itself as a smaller version. Such patterns, called fractals are in fact a visual manifestation of the concept of recursion. One well-known pattern is the Sierpinski gasket, displayed in Figure 18.3.

Figure 18.3: Running `Sierpinski`. Notice how the Sierpinski gasket is composed of eight smaller Sierpinski gaskets arranged around the central white square. This is what will lead to our recursion.

Our recursive method will take three parameters indicating the position of the gasket to be drawn; the first two parameters will indicate the x- and y-coordinates of the gasket's upper left corner, and the third will indicate how wide and tall the gasket should be. The method will immediately draw a white box centered within the gasket, whose side length is 1/3 of the overall gasket's side length. And then it will draw the eight smaller gaskets surrounding that box, each of whose side lengths is also 1/3 of the overall gasket's side length.

The base case will be when the side length goes below 3 pixels. In this case, doing a recursive call is pointless, since the white square to be drawn is such a situation is smaller than one pixel.

The full working program appears in Figure 18.4.

Figure 18.4: The `Sierpinski` program.

```  1  import java.awt.*;   2  import acm.program.*;   3  import acm.graphics.*;   4     5  public class Sierpinski extends GraphicsProgram {   6      public void run() {   7          // draw black background square   8          GRect box = new GRect(20, 20, 242, 242);   9          box.setFilled(true);  10          add(box);  11    12          // recursively draw all the white squares on top  13          drawGasket(20, 20, 243);  14      }  15    16      public void drawGasket(int x, int y, int side) {  17          // draw single white square in middle  18          int sub = side / 3; // length of sub-squares  19          GRect box = new GRect(x + sub, y + sub, sub - 1, sub - 1);  20          box.setFilled(true);  21          box.setColor(Color.WHITE);  22          add(box);  23    24          if(sub >= 3) {  25              // now draw eight sub-gaskets around the white square  26              drawGasket(x,           y, sub);  27              drawGasket(x + sub,     y, sub);  28              drawGasket(x + 2 * sub, y, sub);  29              drawGasket(x,           y + sub, sub);  30              drawGasket(x + 2 * sub, y + sub, sub);  31              drawGasket(x,           y + 2 * sub, sub);  32              drawGasket(x + sub,     y + 2 * sub, sub);  33              drawGasket(x + 2 * sub, y + 2 * sub, sub);  34          }  35      }  36  } ```

## 18.4. Tree

One very nice fractal worth looking at is the tree-like one appearing in Figure 18.5. Unfortunately, our presentation will only make sense if you're familiar with the sines and cosines of trigonometry; but if you understand them, this is worth your while.

Figure 18.5: Running `Tree`. Looking at Figure 18.5, you'll notice that the tree consists of a trunk and two branches. Each branch is appears exactly the same as the overall tree, but smaller and rotated a bit.

In our implementation of Figure 18.6, our recursive method will take four parameters to indicate the trunk of the tree to be drawn. (Below the top level of the recursion, the trunk will in fact be the base of the branch being drawn.) These four parameters indicate the x- and y-coordinates of the trunk's base, the length of the trunk, and the angle of the trunk.

The recursive method's base case will be when the length is at most 2 pixels. In this case, there is not an interesting tree to be drawn, so the method returns immediately. But if the length is more than 2 pixels, the method will compute the coordinates of the trunk's other end of the trunk by applying basic trigonometry. To compute the cosine and sine of the trunk's angle, the method use the static methods `cosDegrees` and `sinDegrees` found in the `acm.graphics` package's `GMath` class. After computing the coordinates of the trunk's other end, the method adds a line corresponding to the trunk. And then it makes two recursive calls to draw each branch. Both branches are slightly smaller than the overall tree (75% in the case of the left branch and 66% in the case of the right), and at rotated at an angle from the trunk (30° counterclockwise for the left branch, 50° clockwise for the right).

Figure 18.6: The `Tree` program.

```  1  import java.awt.*;   2  import acm.program.*;   3  import acm.graphics.*;   4     5  public class Tree extends GraphicsProgram {   6      public void run() {   7          drawTree(120, 200, 50, 90);   8      }   9    10      public void drawTree(double x0, double y0, double len, double angle) {  11          if(len > 2) {  12              double x1 = x0 + len * GMath.cosDegrees(angle);  13              double y1 = y0 - len * GMath.sinDegrees(angle);  14    15              add(new GLine(x0, y0, x1, y1));  16              drawTree(x1, y1, len * 0.75, angle + 30);  17              drawTree(x1, y1, len * 0.66, angle - 50);  18          }  19      }  20  } ```

Playing with the proportions and rotation factors in the recursive calls leads to other interesting tree variants.