Recursion As A Programming Technique

The definition of the factorial function

factorial(0) = 1
factorial(n) = n * factorial(n-1)   [ for n > 0 ].

can be written in C without the slightest change:

int factorial(int n)
{
  if (n == 0) return 1 ;
  else        return n * factorial(n-1) ;
}

Similarly, our strategy for adding up the values in an array can be coded directly as follows:

int addup(int first, int last, int x[])
{ int s1, s2, m ;
       if (first   == last) return x[first];
  else if (first+1 == last) return x[first] + x[last];
  else {
         m  = first + 1 ;
         s1 = addup( first,    m, x);
         s2 = addup(   m+1, last, x);
         return s1 + s2;
       }
 }