Steve Mumford delves into the intricacies of recursion.

You might be glad to know that we're reaching the end of our trek through the basics of C, and it's almost time to start applying our knowledge to more complex applications include those that run in the desktop. However, before we begin that particular quest I'd like to take a moment to investigate an interesting aspect of the language that has a reputation for causing some confusion. To be honest, recursion isn't something that's vital to know about, but if you understand how to apply the methods involved, you can save yourself time and produce some particularly neat and satisfying code.

Self-referencing and recursion

void bottomless(void)
{
  printf("Now we call bottomless() again!\n");
  
  bottomless();
}

The above fragment defines a function that includes a reference to itself in the same way as the structures that we looked at last month.

In this case, the functions prints out a line of text, then calls itself and performs the routine again. In effect it creates an infinite loop, but there's a subtle difference. When a function is called, information concerning what the function was doing was written to something called the stack. It's an area of memory which is used as a form of scratch pad. This is where the computer stores any local variables being used at the time, and the address that it must return to after it's finished executing the current procedure. The stack can cope with more than one entry - if you've called a function which in turn calls another, both return addresses are stored in the correct order. In technical terms, this is known as a last in, first out stack because the newest address stored is always the first one to be returned to.

In the running of a normal program the stack remains quite small due to the fact that there's a finite number of function levels. However, if you include a function that calls itself, it's possible for the stack to grow rapidly as each call to the procedure adds another data entry to the list. If this goes on for too long, the area of memory set aside for the stack can overflow, and - yes, you've guessed it - we witness a crash. You might be wondering how a function that calls itself can ever avoid causing program failure, and the answer lies in providing an escape route which can be used once a certain condition is reached. A popular example of recursion is shown below, and it provides a factorial function:

int fact(int x)
{
  if (x==1)
  {
    return(1);
  } else
  {
    return(x * fact(x-1));
  }
}

The operation of the function is a little hard to describe, and it may help if you've got a bit of paper to doodle on, but here's what happens:

Performing the factorial of a number requires it to be multiplied by all the numbers below it, from one upwards. In order to carry this out, the procedure breaks the task down into individual steps. In common with a lot of recursive alogrithms, there are two distinct phases to the calculation - one is performed as the level of recursion is deepening, and the other comes back into operation while the recursion level works back upwards. In this case, the first task is to work out the extent of the sum - a process which is a little like expanding brackets in algebra. The second half of the routine actually performs the multiplication and hands the result back to the previous level, thus working its way out of the recursion pit.

Whenever the function is called, it checks the value of the number it's been passed. If the value is anything other than one, fact() calls itself to calculate the product of x and x-1, and the execution of the parent function is frozen just before it evaluates the multiplication.

If the number that's been passed to the function is equal to one, this signifies that the end of the calculation has been reached - instead of progressing any further, the function returns with the value 1. This is the turning-point of the whole process and from this point on, the computer will work its way back up the stack, performing all the outstanding multiplications and finally producing a result.

In order to illustrate this, let's assume the function fact() has been called with the value 3. The program makes the comparison mentioned above and then executes the line shown below, with the appropriate values filled in:

return(3 * fact(3 - 1));

At this point, fact() is called once more, and now we're a level deeper into the recursion. Yet again, the comparison is made and contol passes to the line shown:

return(2 * fact(2 - 1));

If we remember that we were halfway through an earlier multiplication when we dropped a level, we can write these two lines down together to form:

return(3 * (2 * fact(1)));

fact() is called one last time, and since the if condition is now successful, no further calls are made - the function returns with a value of one. We arrive in the middle of the previous function with a multiplication that can now be performed. Its result is passed back to the parent and, at long last, the answer to the original question can be produced. The stack has shrunk to its initial size, and the program can continue as normal.

Data structures such as binary trees and linked lists can be more easily handled if recursion is used - for example, if you were using a linked list of 20 elements and you wanted to delete the last 15, you would find yourself having to read and store the pointer to the following element before you deleted the current one - otherwise, the address of the next element is lost and there's no way of recovering them memory. It's perfectly possible this way, but it's a little ungainly. The recursive method steps down the list, checking the next element pointer and calling itself with that value if it's not NULL - in this way, it finds the end of the list. Once the routine discovers a NULL pointer, the recursion switches phase and works its way back, deleting each element as it goes.

Why use recursion?

And now for something completely different

In the meantime, you might like to look over the last few issues and write a few more progeams for yourself. There's no substitute for thrashing out your own software when it comes to learning a language, and it's always amusing to find a new way of crashing your computer - I'd be interested to hear of any particularly spectacular ones. See you next month.