Recursion may be a word you've never heard outside of computer science. But it's actually a concept with pretty deep roots in the study of language and the study of mathematics; more generally, recursion is a form of "self-reference." Some examples:
Hi.
Lance said, "Hi."
Saheed said, "Lance said, "Hi.""
Jen said, "Saheed said, "Lance said, "Hi."""
Juyin said, "Jen said, "Saheed said, "Lance said, "Hi.""""
.
.
.
These aren't super-interesting sentences, but they're perfectly legitimate.What do all these examples have in common? The idea that complex/big things can be built from simple/small things through the application of some rules. (The "rules" in the images aren't explicit, but if you look through the entire collection, you'll quickly see that there are really just a few fundamental techniques that the artists are using.) Or, looking at it from the other direction, recursion is a way to break down complex things into simple things.
Self reference is very very common in computer science. There are lots of recursive jokes in computer science, even. Maybe you've heard of the web language PHP? PHP stands for "PHP: Hypertext Preprocessor." Maybe you've heard of the free software operating system GNU/Linux? GNU stands for "GNU's not Unix." This Wikipedia entry includes a pretty long list of software tools with this kind of name-that-includes-itself; you'll probably recognize at least a few. Perhaps one of the best (or most annoying?) self-reference jokes in computer science appeared in an edition of the the book The C Programming Language. In the index, on page 269, is the index entry for recursion, which reads, "recursion 86, 139, 141, 182, 202, 269". It's pretty unusual for an index entry to list itself!
OK, probably none of this is laugh-out-loud humor. But maybe it gives you a sense of what's going on when we talk about recursion and self-reference in software. So, to get a little more specific about how recursion is useful in computer science: it is most commonly used in certain kinds of calculations (which will be our main focus in this class) and in making certain kinds of definitions (which is very important in data structures—and this is the main reason I want you to have some exposure to these ideas now).
What would it take to write a method that calculated the nth Fibonacci number? Specifically, we want a method int fibonacci(int n) that will (say) return the 5th Fibonacci number if called as fibonacci(5). What's the 5th Fibonacci number? I'm not sure, but I know it's the 3rd Fibonacci number plus the 4th Fibonacci number. I don't know what those are, but I know how to calculate them. Really, the only Fibonacci numbers I know for sure are the 0th number (which is 0) and the 1st number (which is 1). So there's two F-numbers (I'm tired of typing "Fibonacci") that are super-easy to calculate; the rest take some work. So let's try this code:
int fibonacci(int n) {
// let's deal with the two easy cases first:
if (n == 0)
return 0;
else if (n == 1)
return 1;
// the rest of the F-numbers are calculated by summing the two previous F-numbers
else return fibonacci(n-1) + fibonacci(n-2);
}
Read this carefully and make sure the logic conforms to the definition of the Fibonacci numbers. There's obviously something a little unusual about this code: the fibonacci method calls itself! That may feel a little dangerous, or paradoxical, on the one hand; but on the other hand, this method is just applying the definition of "Fibonacci number." (By the way, most programming textbooks start off by saying something like, "the definition of a recursive method is a method that calls itself." I don't think that says very much about why recursion is useful or important, but it is at least part of the story.)
Let's look at another numerical example, then we'll step back and look at what's going on. You may have heard of the mathematical idea of factorial—for example, "6 factorial," written 6! is the product 6 x 5 x 4 x 3 x 2 x 1. Another way to look at it: 6 factorial is 6 times 5 factorial. Or, 6! = 6 x 5!. So this formula shows us how to compute a big factorial (6!) based on the value of a smaller factorial (5!). Of course, that formula gets a little awkward if we try to compute 1! because 1! = 1 x 0!. Fortunately for us, 0! is defined to have the value 1.
We can use that formula to write a recursive factorial method:
int factorial(int n) {
// the easy case--we know that 0! is 1
if (n == 0)
return 1;
else
// otherwise, we can use the formula to calculate our result
return n * factorial(n-1);
}
Hopefully, it's clear that these two methods "match" the formulas for the Fibonacci numbers and for factorial. But that doesn't mean they actually work properly. This is where it's important to have a solid understanding of how the "stack" works. Remember that "the stack" is not only the part of memory that stores local variables but also where the JVM keeps track of the history of methods that have been called (you might want to review these ideas on p. 237 of the textbook). How does the call stack work if you call factorial(0) from main()? What about factorial(1)? factorial(3)? Draw a diagram on a piece of paper. Once you have that done, compare your thinking with the diagram (a sort of blue triangular thing a little ways down the page) here.
You can also try your hand at the fibonacci() call stack, though this is a little bit more complicated because the method calls itself twice. You should see that fibonacci(0) and fibonacci(1) are straightforward; carefully work out what happens when you call fibonacci(2)—then try fibonacci(3). (You may realize that there are some serious inefficiencies here; there are ways to deal with this.)
What you hopefully realized is that even though these methods call themselves, which feels like something that maybe shouldn't be allowed, these actually work perfectly fine, because the "easy" cases cause the calling-itself process to stop. (By the way, note that if we call either of these methods with a negative parameter, we do have a problem—what happens with the call stack if we call factorial(-1)? How could we prevent this problem?) But, assuming we pass a "legal" parameter value, these methods calculate normally. So, an effective recursive method needs to have two sections: at least one "easy" case, which is technically called a base case, and at least one recursive case in which the method calls itself with a value that is smaller (in some sense) than the value it received. Of course, as the Fibonacci method shows, we can have multiple base cases, and sometimes we also need to have multiple recursive cases.
Here is a class that contains several recursive methods; here is a main program that calls those methods. Work with this code to explore what happens when:
if/else)n instead of n-1).
But not every recursive calculation is based on numbers and arithmetic. Let's look at a couple more examples that might be familiar. A palindrome is a sequence that reads the same forwards as it does backwards. The word level is a palindrome; so is the sentence A man, a plan, a canal, Panama. (if you ignore case, spaces, and punctuation). How can we recognize a palindrome computationally? One way is to make a copy of the sequence, reverse it, and then go through character by character making sure everything matches. But we can also observe that a palindrome is built from a smaller palindrome—so a sequence P is a palindrome if P has the form xQx, where x is any character and Q is a palindrome.
That idea gives rise to a recursive approach for identifying a palindrome: given a string, check to see if the first and last characters are the same; if they are, then check to see if the middle section is a palindrome. Let's start writing some code based on this idea (and the Java String API).
boolean isPalindrome(String s) {
// idea: compare first (index 0) and last (index length-1) characters
// if they're the same, test the "middle substring" to see if it's a palindrome
if (s.charAt(0) == s.charAt(s.length()-1))
return isPalindrome(s.substring(1,s.length()-1));
else
return false;
}
Double-check that this uses the charAt() and substring() methods properly. Assuming it does, there's still something missing: there's no base case! (It's maybe a little tricky to see, but the whole if statement is the recursive case.) What should the base case(s) say? Think about the strings "pop" and "noon"—what base case(s) do you need in order for these to be recognized as palindromes? Does your solution also work to reject "cat"? Does it work correctly for "g"?
Before we look at another String example, let's step back for a second. It may have occurred to you that so far, I haven't offered a compelling case that we need recursion. Most everything we've done far we could do just as easily—maybe easier— with a loop. It's easy to write a for loop to calculate factorial. I suggested that one way to identify a palindrome is basically to loop through a sequence and its reverse comparing characters. And it's true: recursion is a kind of repetition, just like loops, and in general, anything I do with recursion I can do with a loop, and vice-versa. (Heck, our textbook doesn't even discuss recursion!) Recursion and loops are both tools—neither of them is absolutely necessary, but each of them have areas in which they are the best tool for the job. I'm discussing these fairly simple calculations because they make it easier to see how recursion works, but no-one is going to argue that recursion is the best way to calculate a factorial in Java. On the other hand (brace yourself): some languages don't have loops. In that situation, recursion is the only way to achieve repetition. And, as you'll see when you take data structures, recursion is a really powerful way to define some data structures (and then to do some calculations on those data structures).
One more String example. How to print out the reverse of a string? That is, we want a method that takes a string like "giraffe" as its parameter, and prints out "effarig." As usual, we could write a loop that "counts down" through the string indices, printing the character in each position. But recursion gives us (or requires us to find) another perspective. What if we realize we can, in general, view any string (like "giraffe") as a (shorter) string with a character added on the end (so, "giraff" + 'e')? Then we could describe the reverse algorithm like this: print out the last character, then print out the reverse of the initial string. In code, it looks like this:
void boolean printReverse(String s) {
// the base case... probably the empty string, with length 0
if (s.length() == 0)
System.out.print(); // note the problem says nothing about printing newline
// idea: print the last character, then reverse the initial part of the string
else {
System.out.print(s.charAt(s.length()-1)));
reverse(s.substring(0, s.length()-1));
}
}
I sneaked that base case in there... how do you figure out what the base case is supposed to be? It tends to relate to the way the recursion works: if each step in the recursion works on a "simpler" form of the problem, then what is the "simplest" form? It very much depends on what what "simpler" means—here, it means "a shorter string." In that case, the "simplest" version of the problem is "the shortest string," that is to say, the string with length 0. In more complictated problems, it can take a little more thought to figure out the relationship between the base case(s) and the recursive case(s). But at the same time, you have to be sure that your base case doesn't exclude anything. For example, imagine that the printReverse code stopped with strings of length 1. What bad thing would happen then?
In those string examples, notice that the recursive step relies on a particular way of looking at a string. For the palindrome example, we viewed a string as an initial character, a final character, and a middle string. For the reversing example, we viewed a string as an initial string and a final character. That is, just for moment, we claimed that strings have a recursive structure, just like some of the images linked above. That idea can be very powerful when applied to searching and sorting. I'll talk a bit about searching here, and leave sorting for data structures.
Hopefully, in 1115 you talked a bit about how to search an array for a particular element. If the array isn't sorted, then this kind of search can take a long time, but if the array happens to be sorted, then this search can be quite fast. You may remember the idea: start with the middle element of the array; if the value you're searching is smaller than the middle, then search in the first half; if the value you're searching is bigger than the middle, search in the second half. This is called binary search, because we're splitting the array in 2 with each pass. To review these ideas, read section 7.4.1 here, which shows code for searching both an unsorted and a sorted array (of int). Once that looks familiar, the read the same book's treatment of the recursive approach to this kind of search here. As you're looking at this code (and the accompanying commentary), check for: what is/are the base case(s) for this algorithm? the recursive case(s)? Stop reading when you get to the 9.1.2 heading.
This kind of idea is also used to create a relatively fast sorting algorithm, though it's a little more complicated (which makes sense... sorting is usually more complicated than searching). Keep your eyes peeled for "merge sort," which is structured very like binary search: the idea is to sort each half of the array, then merge the two sorted halves into one sorted whole. (How do you sort the first half of the array? Well, you sort each half of it, then merge. And so on, recursively.) This is easy to describe, but it's not a terribly efficient sorting algorithm. A better approach is called "quicksort," which has a slightly more complicated approach to dividing the array into two sub-arrays. Feel free to read about it, but we won't be talking about it in this class.
Finally, recursion can be used to define things. One advantage of a recursive definition is that it's usually pretty easy to see how to use recursive algorithms to work on these values. For example, we very nearly wrote a recursive definition of "string" above; let's get a little more precise:
This type of recursive definition may be familiar to you if you've already taken discrete structures... you'll also encounter it for sure in data structures, where it can be used to define not only strings but more complicated structures.