Recursive rights and wrongs

CScript “path\powers.js”

I don't know if Jack Altiere is right when he says many programmers are afraid of recursion, but if it's true I expect they fall into two categories:

1. Those who have not learned what recursion is yet.
2. Those who have learned that it is often better not to use it.

Jack's short introduction is probably good for those in category one, but if you want to ever consider yourself an experienced programmer you should be trying to get into category two. This article is intended to help you get to category two as quickly as possible.

Some simple recursion

Recursive functions are easy. The only thing that you have to do to write a recursive function is to have it call itself. That's pretty easy and you may think that there isn't much reason to use it, but it can be very powerful. It turns out that there are all sorts of things that we might want to do that are easier to think of in terms of recursion. We won't go into all of them here, but if you look through your code you'll probably find that you have plenty of examples of them.

We're going to study a mathematical function that can be handled in all sorts of interesting ways — integer power calculations. I'm going to use Javascript (even though it wouldn't normally be my first choice for this sort of testing) because more people are likely to be able to run the tests themselves if I do so.

For those that have forgotten your basic maths notations this means that we take some number v and multiply it by itself n times. If we take v as 4 and n as 2 we get 16 because 4 × 4 = 16¹ [1We're only going to consider positive integers for both v and n here, but the equation does of course work for any numbers.].

We also need to be aware of a couple of special rules. Anything multiplied by itself no times is one. This seems counter-intuitive, but it makes all the maths work out. Another rule is that anything multiplied by itself once is just the same as itself. We can write these as:

We should put these together to get a complete definition:

Let's take a look at an extended example whilst we remember that our notation means we are multiplying a number by itself² [2There is of course a shortcut that works for any positive values of n and not just integer ones, but this article is about recursion and not logarithms]:

There is a rather striking pattern here which we can express quite simply in an improved program³ [3I'm calling it a program because if we were using a pure functional programming language then this would be the program. The syntax would change depending on which programming language we were using, but the structure of the program would be essentially the same]:

It is this last part of our definition that makes it recursive. We have defined power() in terms of itself and that's all that a recursive function is — a function that calls itself. We can write this in Javascript pretty simply too:

function power_recurse( value, power ) {
	if ( power == 0 )
		return 1;
	else if ( power == 1 )
		return value;
	else
		return value * power_recurse( value, power - 1 );
}

The three parts to the if statement correspond perfectly to the three parts of our definition of power(). The first two are called base cases because they do not involve any extra call to power_recurse(). The last is the recursive call because, well I'm sure you can work it out.

There's a couple of things that we should notice about this:

1. We have to have the base cases in there⁴ [4Although we don't need both — which can we remove? Try it and see]. Without the base cases the function would continue on forever with power becoming a steadily larger negative value.
2. When we call the recursive function we must alter the arguments in some way. Specifically we have to alter the arguments that are involved in the base case. If we don't do this then the base cases can never trigger and we'll also end up in an infinite loop.

For every recursive function that you ever write these two items must always work together, although the interaction isn't always so obvious. If you want to see an example where finding the base case is hard take a quick look near the end of this article.

Converting to a for loop

If we re-examine the pattern we can see that there is another solution that we shouldn't overlook too. Here is the pattern again:

We can see that we're just multiplying n times. Writing this in Javascript is a breeze:

function power_for( value, power ) {
	var result = 1;
	for ( var i = 1; i <= power; i++ )
		result *= value;
	return result;
}

The base cases here are a little more subtle to spot and when you go through how it works you will notice that the second base case is missing altogether. We don't need it and skipping it makes the function much easier to work with.

The other thing to notice is that whereas the recursive version was a single statement, this one uses three⁵ [5Of course it depends on how you count statements, but the point is that the recursive function contains one block, the if statement. This version contains three different items: the variable declaration; the for loop; and finally the return statement.].

To start with there doesn't seem to be much to choose between them. Functional purists would argue that the recursive function is more elegant, whilst many other programmers would probably argue that the for loop more clearly expresses how the calculation is done.

It turns out though that there is a good reason to prefer the for loop over the recursive function in Javascript. Below is a table of execution times (n is the power that we are requesting be calculated). I've had to repeat the calculations many thousands of times in order to be able to measure the time with any sort of accuracy⁶ [6I've also abridged the results. For a complete table see the end of the article.]. Even so there is a lot of noise in the data, but the pattern is still clear enough.

The first question is why did I choose to plot the times against n and not v? The answer is that n is the control variable. That is, the execution pattern of both functions depends on n and not v. Try working out how they would run with a few different values for v and n and you will see that it doesn't matter what v is, the number of times the recursive function calls itself or the number of times the for is executed never changes. Both change dramatically with any change in n⁷ [7A full explanation is beyond the scope of this article, but will be addressed in another article about algorithmic complexity (which sounds more complex than it is).].

The second question is why are the times so different? To answer that we need to think about what the Javascript interpreter⁸ [8I'm going to call it an interpreter as that's what it logically is even if your platform features a just-in-time compiler for Javascript.] is doing.

For power_recurse(), each time the function is called it must copy the two variables value and power. When we request a power of zero then this function call overhead is about the same for both versions and because of the way we have structured the recursive function (with two base cases) then this is the same for a power of one. But once we ask for a power of two then there are twice as many function calls in the recursive version as compared to thefor loop.

So, although both versions are doing essentially the same amount of work in the same way the extra work in the function call overhead makes the for loop much faster⁹ [9I've ducked something to do with my results here. If you stop to think about the implementation of Javascript and the use of big floats you'll realise that most of the actual returns from the functions we've written are going to be NaN or some other floating point error value as they'll overflow. We could have used some large integer add-on for Javascript, but what we are interested here is the call graphs and memory usage of the different implementation and for that it doesn't really matter that they overflow — each implementation overflows at more or less the same place (differences down to rounding errors) and we check that for numbers that are in our normal range we get the same results.]. Now, interesting as this is there are two reasons for this result:

1. The operation at the heart of the calculation, the multiplication, is practically free compared to everything else we're doing. This skews the results dramatically. If we slowed the multiply down by a factor of a hundred then I doubt we would see any difference between them.
2. The Javascript interpreter isn't all that smart (more on this later).

What this means is that although the recursive function incurs an overhead in the function calls and this takes longer this is not the reason why we prefer for loops!

Stack space and heap space

The memory that your computer program uses comes in two flavours and they behave quite differently (actually there are three if we include the memory that the program code sits in, but let's ignore that as it isn't important for this discussion).

The first, and the biggest, is the heap. This is where nearly all of the data that your programs use live. The stack on the other hand is small and is used for remembering where to return to after function calls, the function call parameters and the function's local variables. I'm sure you can see where this is leading.

The for loop version is only ever going to use one function call no matter how big the power we ask for is. The recursive version on the other hand has to remember function return points and variables on each call. For a power of one hundred that's one hundred times as much memory! If the power is big enough we can get Javascript to run out of memory using a recursive function which the for loop could never do.

And this is the reason why we normally prefer to write a loop rather than a recursive function when we can.

Even if the Javascript interpreter uses its heap for the Javascript stack the principle still holds — it just means that the power needed to blow the program up has to be bigger¹⁰ [10Although if the interpreter executed the recursive Javascript call recursively in it's own execution (which it almost certainly doesn't) then you could still exhaust its stack very quickly.]. On my machine power_recurse() exhausts the stack somewhere between n = 1,000 and n = 10,000. These are not high numbers. Even if the stack frame for each function call was one kilobyte (and it's probably actually a few hundredths of that size) then this represents only between one and ten megabytes.

For programming languages like C, C++ and Java though the stack is normally tiny in comparison to the heap. My computer at the moment has a gigabyte of RAM and a further 1½ gigabytes of swap space. My C++ compiler though has a default stack size of only one megabyte (which is still a lot larger than I was expecting), but still represents over three orders of magnitude.

This memory usage overhead of recursive functions is the real reason why recursive functions are often replaced with loops wherever possible. There are two circumstances under which recursive functions have to be very carefully controlled:

1. In library code, especially low-level libraries, the function call and stack overhead are probably completely unacceptable.
2. If the control variable is under user control (either the programmer using your function, or even worse the end user sitting at the computer running the program) then you have not only a software crash waiting to happen but, for server software, a potential vector for attack. It may be possible to inject code (similar to buffer overruns) or to use it for denial of service.

Of course recursive functions aren't all doom and gloom and there are good reasons to use them anyway. In many circumstances recursive functions are the simplest way to express an algorithm and for many recursive functions we can see that we have to pay the extra memory overhead anyway.

The other sort of recursion

What we've seen so far is a special type of recursion, one where only a single recursive call is made. The way that they are used is very almost tail recursion, and some compilers will be able to turn these functions into proper tail recursive forms in order to use a technique called tail call optimisation. This isn't the place to go into this in any more detail, but the outcome is that a good compiler is able to convert these into a for loop.

There is however another type of algorithm that is very easy (almost trivial) to implement recursively but is extremely hard to write as a loop and even when we do manage it we find that the memory overhead is about the same.

I'm going to stick to the example we've been using so far in order to show the form of the recursive calls even though a bit of even more clever maths will enable us to turn the algorithm into a loop.

Divide and conquer

Let's look at our pattern of multiplication again.

If you look carefully you can see that we can split each of these in two. Let's start at n = 2 and go from there:

Each of the powers can be expressed as powers of about half half their size. Can we make use of this in our program in any way? It turns out that this is pretty easy to do with our functional version, especially if we first put in a slight twist:

What we've done is to split it into symetric calls of half the power with odd versions taking an extra factor of × 4. Written functionally this gives us:

I'm assuming that there is a modulus function that performs the standard mathematical operation and that the division by two is an integer division so it throws away the fraction.

Can we implement this in Javascript? Actually it's pretty easy to do so recursively. Again this is the natural way to turn our insight into working software and we end up with this new version:

function power_recurse_quicker( value, power ) {
	if ( power == 0 )
		return 1;
	else if ( power == 1 )
		return value;
	else {
		var r = power_recurse_quicker( value, Math.floor( power / 2 ) );
		if ( power %2 )
			return value * r * r;
		else
			return r * r;
	}
}

Let's see what this does. The two base conditions are identical to our earlier version so that's pretty easy. As in the functional re-write above the only change is in our implementation for larger powers. We do our recursive call to calculate the answer for half the power and then use this, maybe with an extra factor of our value (if the power is odd) to calculate the requested result.

Does it work out any faster? If we think about what it will do now then it will recurse a lot less. If we start at n = 64 it will go to n = 32, then n = 16, n = 8, n = 4, n = 2 and finally hit the base case at n = 1. The other recursive version would go from n = 64 to n = 63 then n = 62 etc. until it also hit the base case at n = 1. The for loop would work up from n = 1 to n = 2 and then n = 3 etc. until it got to n = 64, but both of these would need to do 64 calculations to work out a sixty fourth power. This new version only does seven calls and six multiplications!

Let's look to see how that translates into the timings.

We can see that it is slow at the lower values (they're all pretty quick on the base cases). By the time we get to n = 10 though it is beating the speed of the old recursive version and by the time we get to n = 100 it is about ⅓ faster than the for and a whopping ten times faster than the old recursive function¹¹ [11The fact that the for loop can compete for such high values of n shows us just how high the function call overhead is in Javascript. It is doing more than ten times the number of calculations and is only slightly slower.].

I have a procedural version of this algorithm that I'm saving for another article. Have a think about how you might implement it. A special prize if you manage to come up with a non-recursive implementation of this algorithm that doesn't require any extra storage — it is not easy¹² [12I tried for several whole days to come up with something and didn't manage it. Despite first off wondering if it wasn't possible Jules' very clever algorithm in the forums does solve it.] (and using logarithms doesn't count — it's of this algorithm).

Summary

Recursion is a very powerful tool and it often enables us to spot algorithms that we wouldn't otherwise see. We should however be very careful of using it in production software, especially where the parameters for the recursion ultimately derive from user input, or any other non-trusted source.

• As well as a vector for certain types of denial of service type attacks it could also allow the propogation of worms.
• Even where we have an algorithm that is very hard to express without recursion it may still be worth it in some circumstances simply because the heap is normally so much larger than the stack.

And finally here is a non-obvious recursive program. Try to work out what it does and how it does it. There is a clue in the the function name.

function gcd( value1, value2 ) {
	if ( value2 == 0 )
		return value1;
	else
		return gcd( value2, value1 % value2 );
}

The download file (see top of article) includes this as gcd.js which will show you a table of results to help give you a clue.

See also

• Wikipedia on recursion and [http://en.wikipedia.org/wiki/Tail_recursion tail recursion].
• An example of recursion on Reddit.
• Scheme requires tail-recursion to be automatically handled by the compiler. Note a subtle point here: the compiler must handle it not because of the function call overhead but in order to guarantee that the memory overhead is the same for any call depth. This amounts to a guarantee that you cannot run out of memory and in turn this means it needs a mechanical way to convert the tail recursion to a loop.
• An example of the sort of procedure you may have to go through in order to get your compiler to convert your tail recursion into a loop (or if you're lucky your compiler does it for you).

Full results table

• After n = 100 power_recurse() gets too slow to bother capturing more data. In any case it blows the stack somewhere between n = 1,000 and n = 10,000.
• power_for() is starting to get too slow to capture results after about n = 1,000.
• Also included is the built in function Math.pow() for comparison. Notice that it doesn't get slower for large n. There are good reasons for this and they're called logarithms.