Calling Functions Recursively

---

In C++ a function can call itself. When it does so it is said to be making a recursive function call.

Functions intended to be called recursively are designed differently from ordinary functions. First, they are written to solve a problem that can be solved in a recursive fashion. An example of a problem of this type is one that can be continually divided into smaller pieces until the smallest piece is reached, then, each of the small pieces of the problem is solved and the solved pieces combined to form the whole solution.

Second, a recursive function has to eventually come to a point where the recursion stops. If a recursive function didn’t have this stopping point it would continue to recurse forever. This behavior would eventually overwhelm the resources of the computer on which it was running.

To illustrate the concept of recursion let us examine a simple recursive function that takes an integer argument and recurses based on its value. The name of the function is countInput() and its declaration is given below:

Listing 9.43: countinput.h

1  #ifndef COUNT_INPUT_H 2  #define COUNT_INPUT_H 3 4  void countInput(int input); 5 6  #endif

The function definition for countInput() is given in example 9.44.

Listing 9.44: countinput.cpp

 1  #include "countinput.h"  2  #include <iostream>  3  using namespace std;  4  5  void countInput(int input){  6     static int count = 0;  7     if(count < (input + count)){  8        cout<<"Still counting!"<<endl;  9        count++; 10        cout<<"The input was: "<<input<<endl; 11        countInput(input - 1); 12     } 13  }

Pause for a moment here to study example 9.44. The countInput() function is called with an integer argument named input. On line 6 a static integer variable named count is declared and initialized. The body of the if statement is where most of the action takes place. The variable count is compared with the result of (input + count). If the comparison is true the body of the if statement executes, count is incremented, a message is printed to the screen, and the countInput() function is called recursively with a new argument, namely, input - 1.

The if statement represents the recursion stopping point. If the test is true, recursion continues. If the test result is false, then recursion stops. The following main() function shows the countInput() function in action:

Listing 9.45: main.cpp

 1  #include <iostream>  2  #include "countinput.h"  3  4  using namespace std;   5  6  int main(){  7     countInput(5);  8     return 0;  9  }

Figure 9-14 gives the results of running this program:

Figure 9-14: Results of Running the Simple Recurse Program

Another Example

Although the countInput() function demonstrated the concept of recursion, it does not do a very good job of illustrating how recursion can be used to solve a meaningful problem. To address this I would like to show you a recursive sorting function called quickSort().

The quicksort algorithm, developed by C.A.R. Hoare, partitions an input file into two parts and sorts the subparts. Improvements to quicksort have been made here and there by many computer scientists and the implementation I use below can be found in (Sedgewick). A complete analysis of quicksort is beyond the scope of this book but an excellent treatment can be found in both (Sedgewick) and (Knuth).

The following code gives the declaration of quickSort() and a utility function named swap():

Listing 9.46: quicksort.h

 1  #ifndef QUICK_SORT_H  2  #define QUICK_SORT_H  3  4  void quickSort(int a[], int l, int r);  5  void swap(int a[], int i, int j);  6  7  #endif

The definitions of both functions appear below:

Listing 9.47: quicksort.cpp

 1  #include "quicksort.h"  2  3  void swap(int a[], int i, int j){  4     int temp = a[i];  5     a[i] = a[j];  6     a[j] = temp;  7  }  8  9  void quickSort(int a[], int l, int r){ 10     int i, j, temp; 11 12     if(r > l){ 13       temp = a[r]; 14       i = l-1; 15       j = r; 16       for(;;){ 17         while(a[++i] < temp); 18         while(a[--j] > temp); 19         if(i >= j) break; 20         swap(a, i, j); 21       } 22       swap(a, i, r); 23       quickSort(a, l, i-1); 24       quickSort(a, i+1, r); 25       } 26  }

The swap() function is called in the body of the quickSort() function. swap() simply exchanges array elements indicated by the parameters i and j.

The quickSort() function takes as arguments the array of integers to be sorted, the left index value, and the right index value. On the first call to quickSort(), given an array to be sorted of size N, the argument value for the l parameter will be 0, and the argument value for the r parameter will be N-1. Lines 12 through 21 partition the array based on the final resting position of array element a[r]. Line 22 puts element a[r] in its final sorted position and then the two array partitions are then sorted with recursive calls to quickSort(). The following main() function shows the quickSort() function in action:

Listing 9.48: main.cpp

 1  #include <iostream>  2  #include "quicksort.h"  3  using namespace std;  4  5  int main(){  6      int a[] = {15,200,83,1,22,5,44,77,12,23,99,100,32,64,25,0,40};  7  8      for(int i = 0; i<((sizeof a)/sizeof(int)); i++)  9          cout<<a[i]<<" "; 10      cout<<endl; 11 12      quickSort(a, 0, ((sizeof a)/sizeof(int))); 13 14      for(int i = 0; i<((sizeof a)/sizeof(int)); i++) 15          cout<<a[i]<<" "; 16 17      return 0; 18  }

Figure 9-15 shows the results of running this program:

Figure 9-15: Results of Running the QuickSort Program

---