It is important to match the structure of a program to its design. If we are writing a program to look at all the elements in an array, the design says to iterate from 0 to the size of the array. So, a for loop is called for since it looks like the design.
Other kinds of problems are matched by other kinds of control structures. We will see problems, especially involving lists, where recursion is a good match the problem.
To understand recursion, it is necessary to understand something about how programs are compiled and run. In particular, subroutine jumps are key to understanding recursion.
int F1: foo(int x) { return(x+2); }for this bit, the information recorded would include:
Field Name | Value |
---|---|
Kind | Function |
Name | foo |
Param | int |
Formal name | x |
Return Type | int |
Location | F1 |
main() { // some code goes here L0:y = foo(7); L1:System.out.println(y); // some more code }When it comes time to execute the subroutine foo, there are several things that must happen. We need to record where we are in the program so we can come back when the subroutine is done. This is called the return address. We also need to transfer the parameters to the new program. To do this, we build a data structure called a stack frame. As the name implies, this involves a stack. We use a stack to hold this information to handle nested function calls. If we have the following code:
main() { x = funca(7); } int funca(int x) { int y = funcb(x); return(y); } int funcb(int z) { return(z + 2); }When funca() is called in main, we record where it came from. Then funca() calls funcb(). And again, we record the location. At the end of funcb(), we have to retrieve the return point information we saved before the call to funcb() from funca(). Then, at the end of funca(), we have to retrieve the information we saved when we called funca() from main.
If we used a single place to save the information, the data from the call to funca() from main would be replaced by the data from the call to funcb() from funca(). But if we push the information onto a stack, then, when we return from funcb(), we pop the top information off the stack. Now when we return from funca(), we again pop the information from the stack and go back to main.
So a stack is used to hold the data from a subroutine call. When we execute the call to foo() from main, in the first example code, we create a stack frame. In this case, the frame has two pieces of information. It contains the return address of foo L1 and the value of the parameter, in this case, 7. The PC is set to the address of the function, in this case, F1. Then we start running the code in foo(). Before the first line that we wrote is executed, the parameter value is copied from the stack into a local variable for the function. This local variable is the formal parameter of the function, in this case x. When the function is done, the stack frame is popped from the stack.
The return address is remembered and the value of the return statement is pushed onto the stack. Then the PC is set to the return address and execution picks up where we left it when the subroutine jump was made.
In main, we had a line at L0 that looked like
y = foo(7);Before we go one to line L1, the value on the top of the stack is copied to the variable y. Now the entire process is complete and the program goes on from line L1.
Knowing this will help to understand recursion. You were taught that it is bad practice to define a word in terms of itself, circular definitions. Since computers were never taught this, they are happy to use circular definitions. To the computer, a recursive call is just another method call. It has no interest in the fact that it is calling the same method it is in.
The first thing to know about recursion is that it is always slower and uses more memory that the equivalent non-recursive method. And there is always a non-recursive method. However, in a number of cases, mostly involving dynamic data structures, the algorithms are much simpler when written using recursion.
int summer(int N) { int sum = 0; for(int i = 1; i <= N; i++) sum += i; return sum; } // summerA more mathematical way of describing this is to say this is the sum of integers from 1 to N. So we can write a few rules. If N is 1, the answer is 1. For any other N, the answer is N + sum of integers from N-1 to 1. This is a recursive definition since we use the sum in the definition. But note that we have two cases here. The first case has no recursive definition. In fact, no arithmetic is required at all. The code for this would look like:
int summer(int N) { if(N = 1) return 1; return N + summer(N-1); } // summer
Given the description of how method calls work, this starts to make sense. The call to summer() inside summer() is just another method call. It passes the actual parameter (N-1) to the formal parameter (N) and starts work. Here is some code that demonstrates this.
Something to note about this. The first version of summer() is the way people to this problem. The second way is a reasonable mathematical expression of the problem. In both cases, the code matches the problem and so is easy to follow. The first version is much faster. This is one example of learning to think like a computer. People don't often think recursively, but it is an easy and often clearer way for the computer to do things.
The Quicksort algorithm grew out of work done on merge sorts. A merge sort takes a set of data and breaks it into pieces that are small enough to fit in memory. These were developed in the days when memory was measured in Kbytes and data in Megabytes. Once each of the pieces is sorted (and written back to tape) we merge the sorted sections together. Here is a small example of a merge of two Vectors.
The Quicksort breaks the problem recursively into pieces of length two. These are easily sorted by direct comparison. Then, as the recursion unwinds, the pieces are merged back together. Unlike the merge sort, this is done inside the array passed to the sort routine, without using extra memory for the data. You can see this as if the recursive calls break the one big array into a lot of little arrays.
Think of processing the list the same way we thought of summing numbers above. First we do something to the first element on the list. Then we do the same thing to the rest of the list. If the list is empty, we stop. Here is a version of the list code that uses recursion.
Recursion is a very powerful technique. In the programming language Lisp, it can be the only looping control structure you have, and yet, you can write any program in Lisp that you can in other languages. The trick is to think like a computer and to think in the language you are using.