AntoArts

Recursion is something a lot of people find hard, even mystical. I learned to understand it, and even like it quite a bit, by learning Lisp. Recursion lets you solve problems in very elegant ways, and when you understand it, it will be really natural to you.

But the question is, how do you learn it? No, not just learn to know what it is, but really understand it. There is no magical formula which I have found, it just takes practice. As I said, learning Lisp taught me how to understand recursion. The reason was simply that Lisp more or less forces, or at least encourages, you to use recursion for solving many problems and thus forcing one to practice it.

What is recursion, really?

To solve problems using recursion, you want to have a function call itself, and for each call, solve a smaller problem than the initial problem in order to finally solve the big one. Take a simple example, a function for calculating the sum of all natural numbers up to some value of n (the example is in Java):

public static int sumTo(int n){
  if(n==1){
    return 1;
  }else{
    return n + sumTo(n-1);
  }
}

We could call this function, for instance by typing sumTo(5);. A smaller problem would be the sum of all natural numbers up to 4, or 3, or 2, or just one. This is exactly what this recursive function does; it solves each of the smaller problems.

The sum of all natural numbers up to 1 is 1, and if n is 1, that gets returned by our function (this is called the base case, which every recursive function should have in order to properly finalize execution). The recursive call occurs at line 5. It returns n added to the sum of all natural numbers less than n, thus what we get is roughly:

//The following is called stack winding, which is when we go to the base case
sumTo(5);
  5 + sumTo(4);
    sumTo(4);
      4 + sumTo(3);
        sumTo(3);
          3 + sumTo(2);
            sumTo(2);
              2 + sumTo(1);
                sumTo(1);
                  //The following is called stack unwinding
                  1
              2 + 1 = 3
          3 + 3 = 6
      4 + 6 = 10
  5 + 10 = 15

The above is called a stack trace; they can be useful while starting out with recursion, but when you get experienced with recursion, you won’t need them any more (you will just trust it).

Why do you need recursion? Couldn’t you write the previous function using iteration instead of recursion, like:

public static int sumTo(int n){
  int i, sum=0;
  for(i=1;i<=n;i++){
    sum+=i;
  }
}

Yes, you could. It would probably be faster, too (depending on how the compiler optimizes the code). Yet, there are cases when iteration just won’t work to replace recursion, or where iteration is really, really clumsy or inelegant (on the contrary, recursion is almost always elegant). One problem where recursion is (definitely) superior to iteration is the task of walking through all the directories in a filesystem. Say that we want to print every file on a filesystem, we would do it the following way:

walkthrough(file):
  print name of <file>
  if(<file> is directory):
    for files in <file>:
      walkthrough(files)

The first file would be the root directory, containing all other files and directories. For each file (and directory) found, the name is printed. If we find out that that the file is a directory, we go through its children (subfolders and files) and then, for each of them, we call the function itself, printing the name of each of the children and if any of the children are directories themselves, walkthrough() is called on them, printing their contents as well.

Practice (using Scheme)!

To learn recursion, you will need practice (I’m sorry, as I said, I have no magical formula). I would suggest you to learn Scheme, a minimalist dialect of Lisp. There is a famous computer science book for it, (available online for free), and some using the book (by the authors of the book).

Use Scheme to practice problems using recursion. You can of course use another language, but I would say that some dialect of Lisp would be the best place to learn recursion, as the language itself is very well-suited for solving problems that way.

Some problems that can be solved recursively include:

• Calculating the factorial of n (n!)
• Calculating the sum of values in a list
• Calculating the n:th Fibonacci number
• Calculating the greatest common divisor of two numbers using the Euclidean algorithm
• Traversing directories (write a real solution, don’t use pseudocode as I did)

You can find more information on recursion at Wikipedia, as well as examples.