Recursion

You know how to make methods, and you know how to call methods. (Your very first program did that! Ahhh, those simple days of one-line programs….) When you write methods, you’ll usually fill them with method calls. You can make methods, and they can call methods…see where I’m going with this? Yeah? No?

What if you wrote a method that called itself?

That’s recursion.

Well, on the surface, it’s an absurd idea; if all a method did was call itself, which would just call itself again, it would loop like that forever. (Although this is not technically a loop, it is similar; we can usually replace loops with recursion if we feel like it.) But of course, it could do other things as well and maybe call itself only some of the time.

Let’s look at what our ask method from our psych program would look like with recursion instead of while loops:

Oh, nice! That is smooth, with a capital Smooth…er, as they say. Wow. Now I feel kind of bad about pushing that sorry loop version onto you in the previous chapter. This one is super short, has no unnecessary variables, and has no returns; it just does what it does.

Honestly, I’m a little surprised at how nice that was. I would not normally have thought of using recursion here. In general, I try to use loops when I’m going to be doing the same thing over and over again, and I use recursion when a small part of the problem resembles the whole problem; the classic example is in computing factorials. Maybe I should think about using recursion more often….

Anyway, since I brought them up and since there seems to be some universal law that every introduction to recursion involves computing factorials, we might as well give it a whirl. I’m feeling pretty rebellious, anyway, for not using factorials as my first recursion example, so look at this before the recursion police take me away:

There you are: factorials. For those of you who had better things to do than go to math class (clearly I did not), the factorial of an integer is the product of all the integers from itself down to 1. In other words, the factorial of 3 (written 3!, as if to fool you into thinking factorials are really exciting) is just 3 times 2 times 1, or 6. And 0! is 1 (I could give you a “sound of one hand clapping” sort of argument you may or may not find satisfying, or you could just take my word for it), and the factorial of a negative number is just plain bad sportsmanship.

But these examples have been sort of contrived (though I did end up really liking how ask_recursively turned out). How about a real example?

When I was generating the worlds for the game Civilization III, I wanted worlds with two primary supercontinents; those tend to be a lot of fun and just sort of feel “earthy” and…real. So after I generated the land masses (which was some pretty clever programming there, too), I wanted to test them to see what the sizes of the different continents were. If there were two of relatively equal size (say, differing by a factor of 2 or less) and no others close in size, I’d say that was a pretty good world.

The process, then, was something like the following:

1. Build the world.

2. Find a “continent” (which could be a one-tile island…at this point I wouldn’t know).

3. Compute its size.

4. Find another continent (making sure not to count any of them twice but also making sure each gets counted), and repeat the process.

5. Then find the largest two, and see whether they look like fun to play on.

The fun part (actually, it was all fun, not just this part!) was in computing each continent’s size, because the best way to do that was recursively.

Let’s look at a trimmed-down version. Let’s say we have an 11x11 world (represented as an array of arrays…basically just a grid) and that we want to find the size of the continent in the middle (that is, the continent of which tile (5,5) is a part). We don’t want to count any land tiles belonging to any of the other continents. Also, as in Civilization III, we’ll say that tiles touching only at the corners are still considered to be on the same continent (since units could walk along diagonals).

But before we get to the code, let’s solve the problem in English first. My initial plan was to look at every tile on the map, and if that tile is a land tile on the continent I’m looking for, we add 1 to the running total. The problem, though, is how do we know whether a land tile is on the same continent as some other land tile? There are ways to solve this problem, but they all seemed to be too messy; either I was keeping track of lots of information I didn’t feel like I needed or I seemed to be doing the same computation over and over again.

But then I thought, hey, two tiles are on the same continent if you can walk from one to the other. (That was essentially the operating definition of continent in Civilization III.) So that’s how the code should work! First, you count the spot you are standing on (duh); in this case, that means tile (5,5). Then, you send out eight little guys, one in each direction, and tell them to count the rest of the continent in that direction. The only rule is that no one can count a tile that someone else has already counted. When those eight guys return, you add their answers to your already-running total (which is just 1, from the tile you started with), and that’s your answer.

Brilliant! Except for one tiny little detail…how are those eight little guys supposed to determine the size of the continent? You just shrugged the problem onto them! The only tile you counted was the one you were standing on. This is pretty frickin’ lazy. Which is probably a good thing….

How are your eight little helpers supposed to compute the size of the continent? The same way you do! So somehow, by a bunch of little, lazy, imaginary helpers counting only the tile they are on, you get the size of the whole continent. (We still need to make sure no tile is counted twice, but we can just mark each tile as it is visited to keep track.) Without further ado, behold the magic of recursion.

Drumroll, please….

And there you have it. Even if the world was much, much larger and the continent was totally bizarre and oddly shaped, it would still work just fine. Well, there is actually one small bug for you to fix. This code works fine because the continent does not border the edge of the world. If it did, then when we send our little guys out (that is, call continent_size on a new tile), some of them would fall off the edge of the world (that is, call continent_size with invalid values for x and/or y), which would probably crash on the very first line of the method.

It seems like the obvious way to fix this would be to do a check before each call to continent_size (sort of like sending your little guys out only if they aren’t going to fall over the edge of the world), but that would require eight separate (yet nearly identical) checks in your method. Yuck. It would be lazier to just send your guys out and have them shout back “ZERO!” if they fall off the edge of the world. (In other words, put the check right at the top of the method, very much like the check we put in to see whether the tile was uncounted land.) Go for it! Of course, you’ll have to make sure it works; test it by extending the continent to touch one (or better yet, all four) of the edges of the world.

And that, my friends, is recursion. It’s not really anything new, just a new way of thinking of the same old stuff you already learned.