Recursion

Alcock chooses to introduce recursion toward the end of Chapter 2. I'm not sure I agree with the need for this. Recursion - functions which invoke themselves - is an interesting programming concept, and it does permit very elegant solutions to certain programming problems. On the other hand, there is never a situation where the same effect as recursion cannot be achieved using conventional iteration mechanisms, such as for statements.

In any case, all I will add to Alcock's discussion are the following brief comments:

• When any function is invoked, storage is allocated for its local variables (including parameters, if any).

• This storage will be deallocated when the function terminates.

• Recursive functions are a special kind of function. This may seem trite, but it follows that you need to understand the general concept of a function reasonably well before you try to understand the idea of a recursive function...

• If a function is invoked again while it is still already active - i.e. if a recursive invocation is made - then additional storage is allocated to hold a new set of local variables for this new invocation. Each invocation thus has an entirely separate set of variables and parameters - even though, within each invocation, these are referred to by the same names. There is no confusion because the computer keeps careful track of which invocation is being executed, and therefore which copies of variables or parameters to refer to.

• At first sight it seems that recursive function invocation must be fatal: surely the computer will be caught in an infinite regression, invoking ever more copies of the same function, until something horrible happens (like it runs out of storage to hold any more variables) and the whole thing crashes? This certainly can happen; but recursion can also be made benign. It is made benign by ensuring that, at each nested invocation, something is changing (typically a parameter value); and at some, finite, point, this will result in a copy of the function which does not make a further, nested, recursive call to itself, but instead terminates. That then allows its caller to terminate, and its caller in turn, so that the whole nest of recursive calls can finally unwind, and return control to wherever the very first instance of the function was called from.

• But recursion will only be benign and controlled in this way if you, the software engineer, make it so. Recursion is intrinsically dangerous stuff - use it with extreme caution!