Chapter 15
Programming Problems Using Recursion
15.1 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
15.2 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
15.3 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
15.4 Stack Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
15.4.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
15.4.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
15.4.3 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
15.4.4 Example 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
15.4.5 Stack Sortable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
15.5 Tracing a Recursive Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
15.6 A Recursive Function with a Mistake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
This chapter describes several problems that can be solved using recursion.
15.1 Binary Search
A binary search is an efficient way to search for something in a sorted array. The function
definition should be something like:
int search ( i n t * arr , in t len , i n t key )1
The function search returns the index of key within arr. If arr does not contain this
key, then the function returns −1. The arguments mean the following:
• arr: an array of integers. The elements are distinct and sorted in the ascending order.
• len: the length of the array, i.e., the number of elements in the array.
• key: the value to search for. Think of key as the proverbial needle in the haystack.
Since the array is already sorted, it is possible to quickly discard many elements by
comparing key with the element at the center of the array. If key is larger than that
element, we do not need to search the lower part of the array, i.e., the part before the center
element. If key is smaller than that element, we do not need to search the upper part of
the array. This idea can be generalized such that instead of considering the whole array, we
are only considering a contiguous part of the array. As such, there are four scenarios:
• If the contiguous part of the array has no elements, then it is impossible to find key
and the function returns −1.
• If key is the same as the center of the contiguous part of the array, then the index
has been found, and we return that index.
• If the key is greater than the center element, then the function discards the lower half
(the elements with smaller values) of the array, and considers the upper half.
223
224 Intermediate C Programming
• If the key is smaller than the center element, then the function discards the second
half (the elements with larger values) of the array, and considers the lower half.
These steps continue until either the index is found or it is impossible to find a match.
Fig. 15.1 is a graphical view of the steps:
FIGURE 15.1: In each step, the binary search reduces the number of elements to search
across by half. In the first step, key is compared with the element at the center. If key is
smaller, then it is impossible to find key in the upper half of the array. If key is greater
than the element at the center, then it is impossible to find key in the lower half of the
array. The array must have been sorted before performing a binary search.
// bi narysea r ch . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < time .h >4
#in clude < string .h >5
#d ef in e RANGE 1006
int * arrGen ( i n t size ) ;7
// generat e a sorted array of integers8
s t a t i c i n t bi n arySe archH e lp ( in t * arr , int low ,9
int high , i nt key )10
{11
i f ( low > high )12
{13
return -1;14
}15
int ind = ( low + high ) / 2;16
i f ( arr [ ind ] == key )17
{18
return ind ;19
}20
i f ( arr [ ind ] > key )21
{22
return bin arySe archHe lp ( arr , low , ind - 1, key );23
}24
return bin arySe archHe lp ( arr , ind + 1, high , key ) ;25
}26
int binary Search ( i n t * arr , in t len , i n t key )27
{28
return bin arySe archHe lp ( arr , 0 , len - 1 , key ) ;29
}30
void printArr a y ( i n t * arr , in t len ) ;31
int main ( i n t argc , char * * argv )32
Programming Problems Using Recursion 225
{33
i f ( argc < 2)34
{35
printf (" need a positive integer n ") ;36
return EXIT _FAILUR E ;37
}38
int num = strtol ( argv [1] , NULL , 10) ;39
i f ( num <= 0)40
{41
printf (" need a positive integer n ") ;42
return EXIT _FAILUR E ;43
}44
int * arr = arrGen ( num ) ;45
printAr r ay ( arr , num ) ;46
int count ;47
for ( count = 0; count < 10; count ++)48
{49
int key ;50
i f (( count % 2) == 0)51
{52
key = arr [ rand () % num ];53
}54
e l s e55
{56
key = rand () % 100000;57
}58
printf (" search (% d) , result = % d n ",59
key , bina r ySearch ( arr , num , key ));60
}61
free ( arr );62
return EXIT _SUCCES S ;63
}64
int * arrGen ( i n t size )65
{66
i f ( size <= 0)67
{68
return NULL ;69
}70
int * arr = malloc ( s i z e o f ( i n t ) * size );71
i f ( arr == NULL )72
{73
return NULL ;74
}75
srand ( time ( NULL )) ; // set the seed76
int ind ;77
arr [0] = rand () % RANGE ;78
for ( ind = 1; ind < size ; ind ++)79
{80
arr [ ind ] = arr [ ind - 1] + ( rand () % RANGE ) + 1;81
}82
return arr ;83
226 Intermediate C Programming
}84
void printArr a y ( i n t * arr , in t len )85
{86
int ind ;87
for ( ind = 0; ind < len ; ind ++)88
{89
printf (" %d ", arr [ ind ]) ;90
}91
printf (" n n") ;92
}93
This program introduces the concept of helper functions. Helper functions are common in
recursion for organizing the arguments correctly. In this example, binarySearch has three
arguments; however, the recursive function requires four arguments. Instead of passing the
array’s length, two arguments indicate the contiguous part of the array that remains to be
searched. The range is expressed with the two arguments: low and high.
Please pay attention to how the range changes in recursive calls: The range must shrink
in each call. This ensures that the recursive call chain eventually reaches a terminating
condition. Line 16 uses integer division: If low + high is an odd number, then the remainder
is discarded because ind is an integer. Note carefully that line 23 uses ind - 1 for the new
high index. A common mistake is to use ind instead. This will cause a problem because
it does not guarantee that the range shrinks in recursive calls. For example, consider the
situation where the range has only one element. This occurs when low is the same as high.
Their average ind is also the same. If line 23 were to use ind, then the next recursive call
to the helper function would also have low equal to high. The arguments are unchanged
and the recursion will not end. Similarly, in line 25 the low index must be ind + 1 and
not ind. Another common mistake is using if (low >= high) for the condition at line
12. This is wrong when the array has only one element to check. This function returns −1
without checking whether or not that single element is the same as key.
The source listing above includes a function to generate test cases called arrGen. The
program calls binarySearch ten times. In five of the calls (when count is an even number
at line 51), key is an element of the array and therefore binarySearch should find key.
This program shows a strategy to test the program with known results.
15.2 Quick Sort
Section 9.2 explained how to use the qsort function. This section explains how quick
sort works. As previously mentioned, quick sort uses the concept of transitivity: If x > y
and y > z, then x > z. The algorithm first selects one element from the array: It does
not matter which one. This element is called the pivot. It can be any element in the array.
Some implementations use the first or last element; some implementations use a randomly
selected element. After selecting the pivot, the algorithm divides the array into three parts:
(i) elements smaller than the pivot, (ii) equal to the pivot, and (iii) greater than the pivot.
By dividing the elements into the three parts, the algorithm uses transitivity to avoid
unnecessary comparisons among elements. This algorithm is usually faster than other sorting
algorithms and is called “quick sort”. After dividing the elements into the three parts, the
algorithm then recursively sorts parts (i) and (iii). The program stops when all elements
Programming Problems Using Recursion 227
have been sorted. This occurs when each part has only one element or no element at all.
How does the algorithm divide the array into three parts? One solution uses these steps:
1. Determine the value of the pivot. In this example, the pivot is the first element.
2. Iterate through the original array from left (smaller indexes) to right (larger indexes)
using two indexes called low and high. The initial value of low is one higher than the
index of the pivot. The initial value of high is the largest index of the range being
considered.
3. From the left side, if an element is smaller than the pivot, low increments. If an
element is greater than the pivot, stop changing low.
4. From the right side, if an element is greater than the pivot, high decrements. If an
element is smaller than the pivot, stop changing high.
5. Now swap the elements whose indexes are low and high.
6. Continue steps 2 to 4 until low is greater than high.
7. Put the pivot between the two parts.
Note that by the last step, the array will be ordered such that all of the elements smaller
than the pivot are together, and all of the elements larger than pivot are also together. When
the pivot is placed, it is in the correct position for the final sorted array. The following figure
illustrates the procedure. The pivot is 19, low is 1, and high is 11.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 23 8 31 6 42 28 16 51 33
variable pivot low high
Because 7 is smaller than 19, low increments.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 23 8 31 6 42 28 16 51 33
variable pivot low high
The next value, 12, is also smaller than 19, and low increments again. The next value
is 23 and it is greater than 19. Thus, low stops incrementing.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 23 8 31 6 42 28 16 51 33
variable pivot low high
Following the algorithm, if the value whose index is high is greater than the pivot, then
decrement high. Since 33 is greater than 19, we must decrement high.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 23 8 31 6 42 28 16 51 33
variable pivot low high
Since 51 is also greater than 19, high decrements again.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 23 8 31 6 42 28 16 51 33
variable pivot low high
At this moment, the value whose index is low is greater than the pivot. The value whose
index is high is smaller than the pivot. Now we swap these two values.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 16 8 31 6 42 28 23 51 33
variable pivot low high
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.