Recursion

C functions may call themselves. Here is a program which prints out an integer, digit by digit. We could do this iteratively, finding the digits by successive division by 10, printing the remainder. If so, we get the digits in the reverse order. We want to print the most significant first. Recursion allows us to get the order correct. You need to know that putchar prints out a single ASCII character.

/* Print n in decimal */
void printd(int n)
{
int i;

if (n<0)             /* check if we need a minus sign */
   {
   putchar('-');        /* print the minus sign */
   n= -n;               /* carry on as if positive */
   }

if ( (i= n/10) != 0) /* use int division to right-shift */
   printd(i);           /* recurse */

putchar(n%10 + '0'); /* print the digit */
}

We have seen an example of a recursive program: how do we write such programs in the first place? In our example, the difficulty we had was that we wanted the digits to be printed left to right. We might have said that an informal solution to our problem is:

  printd: { print_left_most_digit; print_the_rest }

In this case we get the recursive solution from noting that print_the_rest is just printd with a different argument. In other words, we wrote printd by supposing we already knew how to do it!

In fact, we do know how to write printd for the case when there is only one digit; and we know how to extract the (leftmost) digits. This is a standard recursive form procedure, albeit the degenerate case. SRF is:

proc_name(something)
{
        ...
if (we_have_finished)
   /* finishing case */
   {...}
else
   /* general case: we have not finished */
   proc_name(something_simpler)
}

What we have is:

proc_name(something)
{
        ...
if (we_have_not_finished)
   proc_name(something_simpler)
        ...
}

Note in particular that we have to have a completion test, and it must be before we recurse. Further, the test must eventually be satisfied, so the procedure must modify something that affects the test (often, but not necessarily, the something_simpler serves this purpose).