Recursion

Original written by Chris Noble and Andrew Hill.
Conversion to HTML and minor edits Richard Kay Nov 2000

Recursion is a powerful programming technique that can be used instead of iteration (loops). In 'C' recursion occurs when a function calls itself. Program slowmult.c shows a program which runs very slowly using a loop. This program calculates np where n is a real number and p is an integer. The calculation is carried out by repeated multiplication in a loop. 

/* slowmult.c
   demonstrates slow multiplication by iteration
   original Chris Noble, edited Richard Kay 29 April 1999 */

#include <conio.h>
#include <conio.h>

int main(void){
  double store,num;
  long int p,n;
  printf("enter a number and a (positive int) power to raise it to\n");
  scanf("%lf%ld",&num,&p);
  store=num;
  if(p>1)
    for(n=1;n<p;n++)
      store*=num; /* make store equal to itself times num */
  printf("the result is %15.6lf\n",store);
  printf("press a key to continue\n");
  getch();
  return 0;
}
The output for inputs of 1.00001 (number) and 10000 (power) is shown below. 
Enter a number and a (positive int) power to raise it to
1.00001 10000
The result is 1.1052
Press a key to continue
Try repeating this program increasing p in steps of 10 if it runs too fast !

Program fastmult.c executes the same problem using a recursive technique. 

/* fastmult.c
   demonstrates fast multiplication by recursion
   Original: Chris Noble, edited Richard Kay 29 April 1999 */

#include <conio.h>
#include <conio.h>

double power(double, long int);

int main(void){
  double result,num;
  long int p;
  printf("enter a number and a (positive int) power to raise it to\n");
  scanf("%lf%ld",&num,&p);
  result=power(num,p);
  printf("the result is %15.6lf\n",result);
  printf("press a key to continue\n");
  getch();
  return 0;
}

double power(double x, long int n){
  /* raises a number to a power with smallest possible
     number of multiplications */
  double a;
  if(n==1) return x;
  a=power(x,n/2);
  if (n%2) return x*a*a;
  return a*a;
}
Function power is called once from function main. Function power calls itself repeatedly until n == 1 when the function will return a value from each of the calls to the preceding call. Note that the context of each function call, i.e. local variable values for a particular level are preserved until the program returns from that level. The output from program fastmult.c is shown below: 
Enter a number and a (positive int) power to raise it to
1.00001 1000000
The result is 
2.68677343000936241000000000000000000000000e+43
Press a key to continue
Note the speed of execution of this program compared to program slowmult.c .

The algorithm is to divide the power by 2 using integer division until the power == 1. The function returns either the square of the previous value returned if the power was even at that level or the square of the previous value multiplied by the number if the power was an odd value.

For example if the number were 2 and the power were 37 and we use sq() to represent the square function, this functionality could be expressed as follows:

237 = 2 * sq(218)
218 = sq(29)
29 = 2 * sq(24)
24 = sq(22)
22 = sq(2)

therefore: 237 = 2 * sq(sq(2*sq(sq(sq(2))))).

2 37 = 137438953472 .

Using this recursive method involves 7 multiplications instead of 36. Calculating 1.0000000110000000 recursively involves 30 instead of the 9,999,999 multiplications which would be required in calculating this value iteratively.

Recursive algorithms are used in many applications. For example to search a folder tree for files matching a search pattern when the starting folder has a number of sub-folder branches each of which can have a number of sub-sub-folder branches etc. searching this tree is achieved by checking local files and then treating each branch from the root as a tree to be searched; the same approach is used to search each branch however distant it is from the root. This complete seach algorithm can be pseudo-coded succinctly as: 

For all local files:
  If the current file matches the file searched for:
    report it.
For all local folders:
  Search folder
Return to calling function.
Another recursion example is the merge sort which involves:

a. dividing the set of items to be sorted into 2 halves,
b. sorting each half and then
c. merging the 2 halves together into sorted order.

For a recursive algorithm not to go on forever and run out of memory, each nested call has to handle a smaller or simpler object or set of objects or problem than the sub-program which called it and to which it must at some time return. Also a special way of handling the problem has to be coded when the problem is small enough to handle directly without
further recursion. E.G when the merge sort has divided the range of values to be sorted in half down to single items there is no need to sort these as a set of one items is already sorted.

Recursive algorithms will use extra memory because a separate copy of each local variable will be stored for each call of the recursive function which has been started but which has not yet returned.

Recursive algorithms are used in games where the computer needs to look ahead a number of game moves, in order to choose a good or a best move. Choosing a good move might involve trying all possible moves from the current position, measuring the strength of each position and then repeating this process for the stonger positions either for a pre-determined amount of time or up to a given depth of analysis.

Sometimes it is difficult to use watch points to see the values of local variables because recursion results in more than one copy of these existing at the same time.

In this situation an alternative technique for debugging is to insert extra outputs of these values using printf() and to program extra execution break points using getch().This enables execution to be paused and local variables viewed until the point at which the bug occurs can be identified. Once this is completed these extra watch and break points can be removed. For example the recursion within the above program can be viewed more clearly using the following additions: 

/* fastmult_debug.c
   demonstrates fast multiplication by recursion with debug statements
   Original: Chris Noble, edited Richard Kay 29 April 1999 */

#include <stdio.h>
#include <conio.h>

double power(double, long int);
int level=0; /* extra global variable to assist debugging by
                counting level of recursion */

int main(void){
  double result,num;
  long int p;
  printf("enter a number and an (positive int) power to raise it to\n");
  scanf("%lf%ld",&num,&p);
  result=power(num,p);
  printf("the result is %15.6lf\n",result);
  printf("press a key to continue\n");
  getch();
  return 0;
}

double power(double x, long int n){
  /* raises a number to a power with smallest possible
     number of multiplications */
  double a;
  int oldlevel; /* local debug variable */
  printf("level of recursion on entry is %d\n",++level);
  oldlevel=level;
  printf("n is %ld\n",n);
  getch(); /* debug breakpoint pause */
  if(n==1) return x;
  a=power(x,n/2);
  printf("the value returned by power is %10.6lf \n",a);
  printf("the level of recursion on exit is %d\n",oldlevel);
  getch();
  if (n%2) return x*a*a;
  return a*a;
}