Recursion

Comments and questions to John Rowe.

To iterate is human, to recurse divine.
Computer Science saying

God is subtle but he is not malicious.
Einstein

Functions that call themselves

Recursion is an extremely simple concept: a function simply calls itself. Of course, a function can't always call itself, that would create an infinite loop, so all recursive functions have some sort of test before they call themselves.

void myfun(some_args) {

 /* Do some stuff */
  if ( some_test)
     myfun(some_other_args);
}

A variation on the above is to do the test inside the function:

void myfun(some_args) {
  if (I_didnt_need_to_be_called)
    return;

 /* Do some stuff */
    myfun(some_other_args);
}

or you may need a combination of the two.

Example: geneology

Suppose a structure for a person consists of their name and date of birth, and a list of their children. You could print out the name of a person and all their descendents with the following pseudo-code:

To print a person and their descendents

1. Print their name and date of birth.
2. foreach child:
   • Print this person and their descendents

(notice that in this case the test to call itself is an implicit one: the list of children might be of zero length.)

When recursion goes wrong

The biggest problem is the internal test or tests: either the recursion never stops or some possibilities get missed out. Consider the following rather over-the-top way of calculating a factorial:

int factorial(int i) {

  if ( 1 > 0 ) // Bug!
    return  i * factorial(i - 1);
  return 1;
}

You can see what it's meant to do but we've written '1' instead of 'i' so it will go on for ever. The first stage of debugging is just to print out its arguments:

int factorial(int i) {

  fprintf(stderr, "i: %d\n", i);
  if ( 1 > 0 ) // Bug!
    return  i * factorial(i - 1);
  return 1;
}

You can get even more details by adding an extra debugging argument to tell you the depth:

int factorial(int i, int depth) {
  int d;

  for(d = 0; d <= depth; ++d)
    fprintf(stderr, "  ");
  fprintf(stderr, "i: %d (depth %d)\n", i, depth);
  if ( depth > 12) {
    fprintf(stderr, "Too deep!\n");
    exit(-1);
  }

  if ( 1 > 0 ) // Bug!
    return  i * factorial(i - 1);
  return 1;
}

Here we have done two things:

• We have added an extra 'depth' argument which we increment by one every time.

• We have indented the output according to the depth.

The latter isn't necessary but it is nice.

Be prepared to add some debugging output to your recursive routine.

Using a wrapper

It may be very inconvenient to add an extra argument to your routine because it is called elsewhere, there are header files, etc. In that case just create a simple wrapper:

int factorial(int i) {
  return  factorial_debug(i, 0);
}