4.6. Recursion

Feel free to skip over this section if you're one of those developers with a fear of recursion; not only is this considered an advanced topic, but it can also literally cause headaches. If you should decide to read on, good for you! The only real way to get over the headaches is to use recursion as much as possible and work your way through them. After all, what's a couple of weeks of pain compared to being able to write some really tight code?

Are you still there? Rats! I guess I'll have to write this part of the chapter. So much for kicking back and watching My Name Is Nobody on DVD.

In its simplest form, recursion occurs when a function calls itself repeatedly to achieve some kind of result. Some examples of functions that readily lend themselves to recursion are mathematical, such as the Euclidean algorithm, the Ackerman Function and the functions to compute factorials, Fibonacci numbers, and Catalan numbers.

When setting out to create a recursive function, one thing to keep in mind is that anything that can be done recursively can also be done iteratively. In fact, sometimes it is actually more efficient to code an iterative function. This is because there are limits on how deep the recursion can go, usually around 32K. Attempts to exceed this built-in limitation will result in a nicely worded error message that essentially means "stack overflow." Keep this in mind when implementing recursive functions.

With the disclaimer about the perils of recursion out of the way, let's examine one of the older examples of recursive algorithms, the Euclidean algorithm. Dating from approximately 200 B.C., the Euclidean algorithm is a method for computing the Greatest Common Divisor of two integers. Listing 4-9 shows a recursive implementation of the Euclidean algorithm.

Listing 4-9. A Recursive Implementation of the Euclidean Algorithm

function gcd(m, n) { if ((m % n) == 0) return n; else return gcd(n, m % n); }

To show how this function works, let's call the gcd function with the values 24 and 18. Because 24 % 18 is 6, the function is called again with the values 18 and 6. Because 18 % 6 is 0, we're done, and the value 6 is returned as the Greatest Common Divisor.

Just in case you were wondering what an iterative version of the gcd function would look like, it is shown in Listing 4-10.

Listing 4-10. An Iterative Implementation of the Euclidean Algorithm

function gcd(m, n) { var t; while(n != 0) { t = n; n = m % n; m = t; } return(m); }