{

### Recursion: Example I In languages in general, we say a procedure or function is recursive if it calls itself. The C language does allow recursion (as does Pascal). For some languages, such as LISP, recursion is actually a major theme. Many of the Unix ``commands'' (keep in mind that these are of course programs, which someone wrote) are also recursive. From example, rm, the Unix remove-file command, has a -r option which is recursive: If one of the files being removed is a directory, and this option is used, then the rm will be applied to all files within that directory, and all subdirectories, sub-subdirectories, and so on. (The cp command has a similar option.) In some applications, use of recursion can lead to a strikingly compact and elegant solution to what may seem to be an otherwise-insurmountable problem. The basic idea of writing a recursive function is as follows: Supppose one has a task from some broad category. Break that task down into one or more new tasks which are of that same category. Write the function to do this category of tasks as consisting partly of one or more calls to itself, with those calls being for performing the new tasks. Our first example of recursion is to implement Quicksort, a technique for sorting an array of elements in smallest-to-largest order. In this case, the ``category'' is sorting. The breaking down of tasks is as follows. For concreteness, suppose the array to be sorted consists of ` 12 5 66 13 8 35 29 88` Let us choose the first element, 12, as our pivot element. Now, form two subarrays, consisting of all those original array elements which are smaller than, and larger than the pivot element, respectively: ` smaller: 5 8` ` larger: 66 13 35 29 88` So now we are faced with two new tasks ``of the same category,'' i.e. the sorting category, as the original one--sorting the smaller list, and sorting the larger list. So, let's sort them: ` smaller: 5 8` ` larger: 13 29 35 66 88` Now string together three items--the smaller array; the pivot element; and the larger array: ` 5 8 12 13 29 35 66 88` Now our original array is sorted! The key point was that the all the elements in the smaller array were smaller than the 12, and all the elements in the larger array were larger than the 12--so we naturally get the correct order by merely stringing these three arrays together. Below is a recursive function to do Quicksort, along with a main program and data with which to test it. The implementation here has been chosen for the sake of clarity, not efficiency. The one available in the C library is more efficient (use of this function will be discussed in another handout). ``` 1 Script started on Wed May 6 13:19:52 1992 2 heather% cat Q* 3 4 5 /* function QuickSort(), and program to test it */ 6 7 8 int X, /* test array */ 9 N; /* length of X */ 10 11 12 /* function to do a quick-sort of integers; note that both this 13 version and the one in the text are recursive, but the one here 14 has sacrificed efficiency and generality for clarity */ 15 16 void QuickSort(IntArray,N) /* sort the IntArray array of N elements */ 17 int IntArray,N; 18 19 { int Smaller,Bigger,ComparisonValue,SmallJ,BigJ,I; 20 21 if (N <= 1) return; /* array nonexistent or already sorted */ 22 23 /* idea: put all the elements smaller than IntArray into 24 the array Smaller, and all the ones bigger than IntArray 25 into the array Bigger; then sort Smaller and Bigger; then 26 put it all back together again into the big array IntArray */ 27 28 ComparisonValue = IntArray; 29 SmallJ = BigJ = 0; 30 for (I = 1; I < N; I++) { 31 if (IntArray[I] <= ComparisonValue) 32 Smaller[SmallJ++] = IntArray[I]; 33 else 34 Bigger[BigJ++] = IntArray[I]; 35 } 36 37 /* at this point there are SmallJ values in the array Smaller, 38 and BigJ values in the array Bigger; now sort them */ 39 40 QuickSort(Smaller,SmallJ); 41 QuickSort(Bigger,BigJ); 42 43 /* put it all together now, exploiting the fact that all the 44 elements in Smaller are smaller than ComparisonValue, and 45 all the elements in Bigger are bigger than it */ 46 for (I = 0; I < SmallJ; I++) IntArray[I] = Smaller[I]; 47 IntArray[SmallJ] = ComparisonValue; 48 for (I = 0; I < BigJ; I++) IntArray[SmallJ+1+I] = Bigger[I]; 49 50 /* done; IntArray is now in order */ 51 } 52 53 54 main() 55 56 { int I,Tmp; 57 58 printf("enter array, with ctrl-d to end\n"); 59 for (N = 0; ; N++) { 60 if (scanf("%d",&Tmp) == -1) break; 61 X[N] = Tmp; 62 } 63 QuickSort(X,N); 64 printf("sorted array:\n"); 65 for (I = 0; I < N; I++) printf("%d\n",X[I]); 66 } 67 68 69 70 heather% cc -g Q* 71 heather% a.out 72 enter array, with ctrl-d to end 73 124 22 10 195 200 15 6 99 166 74 sorted array: 75 6 76 10 77 15 78 22 79 99 80 124 81 166 82 195 83 200 84 heather% e 85 heather% 86 script done on Wed May 6 13:21:02 1992``` Analysis: The function basically follows the outline mentioned above, i.e. forming the two subarrays, sorting them, and then putting the results together. A couple of points need to be mentioned, though: In any recursive function, there is some special case of the task which is handled directly, rather than via further calls. In the example here, that special case is checked on Line 21. This is what makes a set of recursive calls eventually terminate. Here, for instance, there will be more and more calls, each one of which splits the current array into two subarrays, etc., so eventually these calls will be on subarrays consisting of only one element; when that happens, Line 21 will ensure that no further calls are made. These considerations should be kept in mind when you are debugging. On the other hand, at the time you are writing the program, you should not think about the continuing sequence of calls which actually get made; you should only think about how to convert the original task into one or more smaller tasks.

Norm Matloff
Wed Nov 8 17:35:37 PST 1995