This lecture is about recursion. Recursion is perhaps the most powerful programming technique, but unfortunately it also commonly referred as the most difficult to grasp. To put it simply recursion is a programming technique which let us to solve problems by decomposing the problem into smaller instances of the same problem. This technique is so powerful that it lets us to even emulate the different kinds of loops with recursion. For instance some programming languages such as Haskell and ML does not have loops at all. Instead recursion is used for everything. Other programming languages like SmallTalk offer tools which look like loops, but actually this are just methods which are defined in different classes and are implemented by using recursion.
The difficulty in grasping recursion is perhaps rooted in the fact that it requires a bit different way of thinking. One of the pioneers in programming languages, Peter Deutsch, said "To Iterate Is Human, To Recurse Divine". A more humorous illustration goes: "To understand recursion, you must first understand recursion." In this lecture will look into three examples of problems that can be solved recursively.
The Fibonachi sequence is a sequence of numbers which often appear in math, art and computer science. The definition of the sequence is:
Fn = Fn-1 + Fn-2.
It is not difficult to compute the n-th number in the sequence by using a loop:
public static int fib(int n) {
int a = 1, b = 1;
for (int i = 0; i < n-1; i++) {
int c = b;
b = a + b;
a = c;
}
return b;
}
However, although this solution is correct, it is not very easy to match the original mathematical definition with the implementation. The original idea is burried inside the implementation. A lot cleaner implementation is possible by using recursion. Note that we can view the sequence as a function which maps numbers into numbers. The mathematical definition above simply says that F(0) == 1 and F(1) == 1. Further on F(n) = F(n-1) + F(n-2). We can transform this directly into Java code:
public static int fib(int n) {
if (n < 2)
return 1;
else
return fib(n-1) + fib(n-2);
}
Here we first check whether n < 2 in which case we simply return one. If this is not the case then we simply call again the function fib to compute the previous Fibonachi numbers, at the end we just return their sum.
This works fine because every time fib is called with an argument which is smaller than the current value of the argument n. In other words if we want to compute for example fib(3) then this is decomposed into the following calls to fib:
fib(3) = fib(2) + fib(1) = fib(1) + fib(0) + fib(1) = 1 + 1 + 1 = 3
At the end the argument will become less than or equal to two at which point we just return one. This is a common pattern in recursive algorithms. There are always one or more basic cases for which there are a predefined values. In all other cases the value is computed by combining several smaller instances of the same problem. When the problem is becoming smaller and smaller it must always converge to one of the base cases.
Unfortunatelly the recursive definition is cleaner but a lot more inefficient. This is easy to see by trying to compute the first 45 numbers in the sequence. The version with the loop computes the numbers immediatelly while the recursive version takes a considerable amount of time. The problem is not in the fact that we use recursion but in the way in which we do it. Note that in order to compute fib(n) we must first compute fib(n-1) and fib(n-2). The computation of fib(n-1) on the other hand also depends on fib(n-2). This means that fib(n-2) will be computed twice. In general the computation of fib(n) involves a lot of repeated subcomputations. At the end it turns out that the recursive algorithm has exponential complexity, i.e. O(exp(n)), instead of O(n) as in the case with the loop. This can be solved by organizing the recursion in a different way:
public static int fib2(int a, int b, int n) {
if (n <= 0)
return b;
else
return fib2(b,a+b,n-1);
}
public static int fib(int n) {
return fib2(1,1,n-1);
}
Now this recursion works in a way which is a lot more similar to the implementation with the loop, but again the code is not that much cleaner.
The Fibonachi numbers are cannonical example for recursive functions but the exponential behaviour of the recursive definition makes it a lot less attractive. The next two examples show problems where the recursion is really the best solution.
The Hanoi Tower is a mathematical puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a stack in ascending order of size on one rod, the smallest at the top. The aim of the puzzle is to move the entire stack to another rod, obeying the following rules:
Lets call the rods "A", "B" and "C". The puzzle is easy to solve once we observe that moving n disks from rod "A" to "B" is possible by first moving the top (n-1) disks from "A" to "C", followed by moving the largest disk from "A" to "B" and finally by moving the (n-1) disks back from "C" to "B". The movement of (n-1) disks is an instance of the same problem. The only difference is that we exchange the roles of the rods. This means that we can solve the problem recursively by decomposing the problem into two smaller problems. We also need a basic case. This is the situation when we have zero disks to move. In such case we don't have to do anything. The implementation of this strategy is the following:
public static void hanoi(String from, String to, String other, int n) {
if (n == 0)
return;
hanoi(from, other, to, n-1);
System.out.println(from+" -> "+to);
hanoi(other, to, from, n-1);
}
When you look at the implementation it might look like this method doesn't do anything. It just repeatedly calls itself and occasionally it prints something. The trick is that every time when we do a recursive call to the same method we call it with different values for the arguments "from", "to", "other" and "n". The Java interpreter keeps a stack with the values of all arguments for every method call. When we make a new call this adds a new entry on top of the stack with the new values of the arguments. This entry stays as long as the method is still executing.
This is illustrated in the slides bellow. On the left-hand side of every slide you see the current state of the stack. On the upper right corner you see the code for the hanoi method. On the lower right corner is the output printed from the program. In the code, the line that is about to be executed is in bold font. You can see the current line and then on the next slide you see the effect of executing this line. Everytime when we do a recursive call this adds a new entry in the stack which contains the new values for the parameters. It is actually the stack where most of the work happens. It is used to keep track of how many disks needs to be moved and in what direction.
The Sierpinski triangle is one example of a fractal structure:
The fractals are amazing geometric objects which has the property to be self similar, i.e. we can take some part of the fractal and after appropriate scaling and translating we will see that the part is actually isomorphic to the whole structure. In the picture above it can be seen that the Sierpinksi triangle is composed of three parts that have the same structure as the whole triangle.
This self similarity relates the fractals to recursion in programming. Indeed recursion is a way to solve problems by composing smaller instances of the same problem. In the case with fractals the smaller instances correspond to parts of the fractal. The algorithms for drawing a fractals necessary involve recursion.
In order to draw a Sierpinksi triangle we need to know the starting position, i.e. the coordinates of the lower left corner, and the size of the triangle. The drawing itself is done recursively by drawing three other triangles with half size. The triangle at the top and the one to the left need to be shifted with half the length which the triangle at the corner is always at the same coordinate.