Recursion

In my personal experience, recursion is a topic that takes many students aback. It certainly knocked me over at my first few goes at it. Why?

Of course, this portion is a monologue, so such questions are purely rhetorical. I'll answer it for myself. For all these reasons, I learned recursion to be an evil thing:
1.) It's more complicated to understand than iteration.
2.) Anything recursive can be expressed iteratively with a stack, so there isn't any point.
3.) It uses more memory than iteration, to the point where you can eat the entire stack.
4.) It's slower than iteration.


Wow. What a useless feature. The original FORTRAN got it right when it didn't allow it. What? There are entire paradigms that discourage iteration in favor of recursion? They must be awful.

Ahhh! This was seriously the type of instruction I've received from three different instructors. I've heard similar experiences from other CS students. It seems the CS people tend not to like recursion.

But then, one fine day, a math professor of mine decided to explain recursion. In 20 minutes. I didn't think it was possible. Past instructors of mine typically spent a week on the subject, and even then no one understood it. I prepared for the worst.

The professor began by writing down the first few terms of the Fibonacci sequence. He talked about it a bit, then wrote down how to arrive at any term:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

That was it. There was no writing out a call stack to get the correct sequence to generate F(5), or explanation of how the functions are exactly are going to return their values. It's math; what's a call stack?

With this example, I got recursion. There are one or more base cases, and a recursive case. As long as you can reach a base case from the recursive case, it will eventually terminate. The problem with all my previous instruction is that it absolutely focused on the nitty-gritty, all the tiny details needed to arrive at a solution. Of course recursion sounded terrible in this construct. When you get that low level, you completely take away the declarative nature of recursion, reducing it to something imperative. Worse yet, all my CS instructors would explicitly go through every recursive call. This is tantamount to needing twice as much time to explain "for 0 to 10" as opposed to "for 0 to 5".

In this way, I feel that my first point is just plain completely untrue. This feeling is an artifact of how it has been taught. Personally, I feel that recursion tends to be easier to understand, and often requires less code. The base case often doubles as a catch for edge conditions, such as an empty list or null (which are common base cases). Additionally, recursion tends to flow more naturally with my thought process. Take the car-cdr design pattern, wherein one processes the head of a list, then recursively processes the rest of the list. With recursion, I first write out my processing logic, then pass off the rest to a recursive call. With iteration, I first have to worry about setting up a loop to go over the list, then write the processing code. I have the short-term memory of a goldfish, and halfway through writing the loop syntax I often forget about what processing I need to do.

Now for point #2. It's absolutely true. Recursion uses the call stack as an implicit stack, as opposed to an explicit stack. However, keep in mind that if iteration is used instead of recursion, one must then manipulate the stack. There must be extra code for a stack somewhere, and processing logic is going to be cluttered up with push/pop calls. The recursive version will almost assuredly be less code, and require less mental overhead to understand. There is just plain something elegant about a recursive DFS on a tree.

Ahh yes, points #3 and #4. Performance is the mind killer (no, I have no read Frank Herbert's Dune, but I hear it's excellent). This is a definite maybe. A maybe elucidated via a cute little exercise/tangent.

Consider the factorial function (!). As a reminder, 4! = 4*3*2*1 = 24. Consider the following iterative implementation, where N is the number to get the factorial of:

int result = N;
for( int x = N - 1; x > 1; x-- ) {
result *= x;
}
return result;

This seems to work. Except for one little bug: 0! = 1, and this will return 0 on that input. Drat. You could probably rewrite the code a bit to make this slip through ok, but the simplest thing to do is to check for it like so:
int result = ( N == 0 ) ? 1 : N;

Darn edge cases. But wait, recursion can actually use edge cases as part of the main logic. So here we have a recursive definition, in LISP:

(defun factorial (N)
(if (= N 0 ) 1
(* N (factorial (- N 1 )))))

Cool. That's a bit shorter, and it actually uses that pesky edge case as a base case. This take advantage of the fact that N! is really N*((N-1)!). Eventually, N-1 will be 0, which is the base case.

But the careful reader notices that this isn't the same as the iterative definition. The iterative definition uses a constant amount of memory. However, this uses an amount of stack space linearly proportional to N. N must be decremented until 0 is reached, at which point all the multiplications occur as individual calls return. Not only does this eat up stack, it's going to take time to unwrap all those calls. Recursion sucks!

But wait! What if this definition were tweaked a bit, like so:
(defun factorial (N)
(factorial-rec N 1)
(defun factorial-rec (N accum)
(if (= N 0) accum
(factorial-rec (- N 1) (* N accum))))

This accomplishes the same thing, but there is a twist now. The decrementing and multiplications occur before the recursive call is made. Each call doesn't need to store any local variables, because they will not be used after the recursive call is made. This is called tail recursion, where the last call made by a function is the recursive call. In the previous implementation, the multiplication was the last call. By utilizing an accumulator that stores the answer as it is processed, one can achieve this.

If your language is smart, it will notice this, and perform a tail recursion optimization on it. (By smart, I mean read the manual. Most functional and logical languages support it, including ANSI-compliant Common LISP implementations, Scala, and Prolog.) This means that internally the code will perform an imperative style goto to the top of the function, as opposed to an actual call. This causes the function to use a constant amount of stack space, although it looks and feels like recursion. If this happens, then points #3 and #4 are null.

"But that used just as much code as the imperative definition!". Yeah, it did. Plus, the imperative definition is a tad easier to read. I said tends to be more elegant, not always.

I'm not saying that recursion should be used for everything, I'm saying that it tends to be underutilized due to improper instruction. In a language that doesn't support tail recursion optimizations, anything that can be made tail recursive should be expressed iteratively anyway. Points #3 and #4 are big, and if your language can't do it for you then usually you're out of luck. (One exception to this is amazingly FORTRAN; see http://www.esm.psu.edu/~ajm138/fortranexamples.html.) Understanding and using recursion is vital for anyone who does a significant amount of programming, and it's not really possible to get into functional or logical programming without it.