Recursion is a strategy that can be applied to problems that have recursive structure. A problem has recursive structure if the problem to be solved can be expressed in terms of a smaller version of the problem.
Everyone's favorite example of a recursive problem is the problem of computing the factorial n! of an integer n.
This problem has recursive structure, because the problem (computing n!) can be expressed in terms of a smaller version of the same problem via the relation
n! = n*((n-1)!)
This simple, recursive relationship leads immediately to the beginning of a recursive implementation of this function in C++:
int factorial(int N) {
return N*factorial(N-1);
}
This captures the spirit of the recursive mathematical relationship. What we see in this code is an example of a recursive function call: a situation where a function is calling itself with a slightly different parameter.
This is perfectly legitimate programming practice, but you do have to watch out for one very important problem, infinite recursion. At it stands, this code will not work correctly, because when we call the factorial function it will proceed to call itself through an infinite regress of function calls. The solution for this problem is to build in a base case test that stops the recursion when the problem has become simple enough to solve without further recursion.
int factorial(int N) {
if(N > 1)
return N*factorial(N-1);
else
return 1;
}
Here we have taken advantage of the identity
1! = 1
built into the complete definition of the factorial function.
We continue our survey of recursion with another simple example. The problem is to convert an integer to a string, including commas. This is a problem with a simple recursive structure, because the problem of expressing the entire integer as a string can be reduced to the problem of combining the character equivalent of the last digit with the string for the other digits. We strip digits off from the end rather than from the front because it is easy to do so by use of the mod operation (%). This problem has an obvious base case: when the number falls below 10 we convert the number to a single digit string and return that string.
A further feature of this problem is the need to pass additional state information to the recursive function. After every third digit we have to insert a comma, so we need the parameter k to keep track of which digit we are working with.
// Helper function to convert single digit integers to strings
string digitToString(int n) {
return string(char('0' + n));
}
// The recursive function
string toString(int n,int k) {
if(n < 10) // base case
return digitToString(n);
else if(k%3 == 0)
return toString(n/10,k+1) + "," + digitToString(n%10);
else
return toString(n/10,k+1) + digitToString(n%10);
}
// Wrapper function to start the recursion
string toString(int n) {
int place = 1;
return toString(n,place);
}
This simple example demonstrates many of the basic features of recursion that we are going to encounter in all of our examples.
The function may need additional parameters to pass in additional state information.
Many problems involving lists have a natural recursive structure. We call problems that can be solved by breaking a list into into smaller pieces and solving recursively divide and conquer problems.
Binary search is the classic divide and conquer problem.
bool search(const vector<string>& A,const string& word) {
return search(A,word,0,A.size() - 1);
}
bool search(const vector<string>& A,const string& word,
int start,int end) {
if(end <= start) // base case
return (A[start] == word);
else {
int mid = (start + end)/2;
if(A[mid] < word)
return search(A,word,mid + 1,end);
else if(A[mid] > word)
return search(A,word,start,mid - 1);
else
return true;
}
}
Merge sort
Merge sort is a sorting algorithm that sorts a list by dividing it into two halves, recursively sorting the halves, and then merging the halves back together again.
void mergeSort(vector<int>& A,int start,int end) {
int n;
if(start >= end) // base case
return;
// divide the range in half
int mid = (start + end)/2;
// copy the first half of the range into a temporary vector
vector<int> firstHalf(mid - start);
for(n = start;n < mid;n++)
firstHalf[n-start] = A[n];
// recursively sort the first half
mergeSort(firstHalf,start,mid-1);
// copy the second half into a temporary vector
vector<int> secondHalf(end - mid + 1);
for(n = mid;n <= end;n++)
secondHalf[n - mid] = A[n];
// recursively sort the second half
mergeSort(secondHalf,mid,end);
// merge the two sorted vectors together
int first = 0;
int second = 0;
n = start;
while(first < firstHalf.size() &&
second < secondHalf.size()) {
if(firstHalf[first] <= secondHalf[second])
A[n++] = firstHalf[first++];
else
A[n++] = secondHalf[second++];
}
while(first < firstHalf.size())
A[n++] = firstHalf[first++];
while(second < secondHalf.size())
A[n++] = secondHalf[second++];
}
void mergeSort(vector<int>& A) {
mergeSort(A,0,A.size() - 1);
}
Both of these are classic examples of divide and conquer recursions. In both cases it is possible to split the original problem into halves cleanly and then process one or both halves by recursion.
An especially important aspect of the second example is the fact that this algorithm modifies its input data. This requires that the separation between different parts of the input data be done cleanly, so that changes to one portion of the input data do not affect other function calls. This also requires us to take into account the fact that data we pass to the recursive calls will be modified by those calls. In fact, this algorithm depends on that behavior.
Perhaps the most famous recursive algorithm designed to operate on lists is quicksort. The quicksort algorithm was developed in 1965 by C.A.R. Hoare, and is probably the most effective general-purpose sorting algorithm for arrays. Here is the source code for one implementation of quicksort.
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
int median(vector<int> & a,int first,int last)
{
int mid=(first+last)/2;
if (a[first] < a[mid])
{
if (a[mid] < a[last])
return mid;
else if (a[first] < a[last])
return last;
else
return first;
}
else
{
if(a[first] < a[last])
return first;
else if(a[last] < a[mid])
return mid;
else
return last;
}
}
int partition(vector<int> & a,int first,int last)
{
int p=first;
swap(a[first],a[median(a,first,last-1)]);
int piv = a[first];
for(int k=first+1;k<last;k++)
{
if (a[k] <= piv)
{
p++;
swap(a[k],a[p]);
}
}
swap(a[p],a[first]);
return p;
}
void quickSort(vector<int> & a,int first,int last)
{
if (last - first > 20)
{
int piv = partition(a,first,last);
quickSort(a,first,piv);
quickSort(a,piv+1,last);
}
else
{
selectionSort(a,first,last);
}
}
void quickSort(vector<int>& a)
{
quickSort(a,0,a.size());
}
Quicksort consists of several parts. The quickSort function above with three parameters is the main recursive function that is responsible for running the algorithm. A key step in the quicksort process is the partition step, which is implemented by the partition function above. The partition step takes a range of the array and rearranges it to make it closer to being sorted. To partition, we start by selecting one of the values in the range and making it be the pivot value. We then rearrange the values in the range into numbers that are less than or equal to the pivot, the pivot, and numbers greater than the pivot. The numbers that end up in the sub-ranges on either side of the pivot are not sorted, but the entire range does end up being slightly closer to being perfectly sorted after each partition.
The partition step then combines with recursion to finish the job. After partitioning the range, we recursively sort the two sub-ranges created by the partition step. This divide and conquer strategy is effective at sorting the entire array.
The recursion works most efficiently in cases in which the two sub-ranges generated have roughly equal sizes. To give a better chance of producing this result, it helps to pick a good pivot value. This implementation uses a median of three strategy to improve the odds of picking a good pivot. We examine the elements at the beginning, the middle, and the end of the given range, and select the median of those three numbers to be the pivot value. That improves the odds of success above the simple approach of always arbitrarily using the first, middle, or last value in the range as the pivot.
The final detail is setting up an appropriate base case. One obvious base case would be to stop when the range [first,last) has size 1 or smaller. The implementation of quicksort shown here simply stops dividing the array into sub-ranges when the range it is handed has size smaller than 20. For ranges that small, any simple sorting algorithm will suffice, so the base case is to call selectionSort to handle any small sub-ranges created by the divide-and-conquer process.