Programming Problems Using Recursion 233
C
C
The following implementation generates all permutations of an array. It requires a
command-line argument to set the array length.
// permute .c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < string .h >4
void printArr a y ( i n t * arr , in t length )5
{6
int ind ;7
for ( ind = 0; ind < length - 1; ind ++)8
{9
printf (" %c ", arr [ ind ]) ;10
}11
printf (" %c n" , arr [ length - 1]) ;12
}13
void swap ( i n t * a , i nt * b )14
{15
int s = * a;16
* a = * b ;17
* b = s ;18
}19
void permute Help ( in t * arr , int ind , i n t num )20
{21
i f ( ind == num )22
{23
printAr r ay ( arr , ind ) ;24
return ;25
}26
int loc ; // d e stinatio n of arr [ ind ]27
for ( loc = ind ; loc < num ; loc ++)28
{29
swap (& arr [ ind ], & arr [ loc ]) ;30
permut eHelp ( arr , ind + 1 , num );31
swap (& arr [ ind ], & arr [ loc ]) ; // swap back32
}33
}34
void permute ( in t * arr , i n t num )35
{36
permut eHelp ( arr , 0, num );37
}38
int main ( i n t argc , char * argv [])39
{40
i f ( argc != 2)41
{42
return EXIT _FAILUR E ;43
}44
int num = ( in t ) strtol ( argv [1] , NULL , 10) ;45
234 Intermediate C Programming
i f ( num <= 0)46
{47
return EXIT _FAILUR E ;48
}49
int * arr ;50
arr = malloc ( s i z e o f ( i nt ) * num ) ;51
int ind ;52
for ( ind = 0; ind < num ; ind ++)53
{54
arr [ ind ] = ind + ’A ’; // ele m ents are ’A ’, ’B ’, ...55
}56
permute ( arr , num ) ;57
free ( arr );58
return EXIT _SUCCES S ;59
}60
Lines 28 to 33 are the core that generates the permutations. One way to understand
how this works is to check the number of iterations generated. When ind is 0, the loop
iterates num times. When ind is 1, the loop iterates num − 1 times. When ind is 2, the
loop iterates num − 2 times. Finally, when ind is num − 1, the loop iterates only once. This
program will iterate num × (num − 1) × (num - 2) ... 1 = num! times. This is the number
of permutations for num items. If all the lines are unique then they are guaranteed to be the
correct permutations.
You may be wondering why loc starts at ind, because when loc is ind, line 30,
swap (& arr [ ind ], & arr [ loc ]) ;1
has no effect. It is true that swapping an element with itself has no effect. However, this is the
way to keep this element at the original location. Without this line, the element will never
stay in the original location. For example, if A is the first element, and loc starts at ind + 1,
then A is always swapped away from the first location, and no generated permutation will
begin with A. As a result, the program will fail to generate all possible permutations.
A different approach can be used to generate combinations. Instead of permuting an
array storing the items, an array is used to store whether a particular item is selected or
not. For example, if arr[0] is 0, A is not selected. If arr[0] is 1, then A is selected. If
arr[2] is 0, then C is not selected. If arr[2] is 1, then C is selected. The helper function
requires five arguments:
1. arr is a binary array storing whether an element is selected or not.
2. ind is the index of the item being decided on whether it is selected.
3. num is the total number of items.
4. sel is the number of items to be selected.
5. sum is the number of items already selected.
// combine .c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < string .h >4
void printArr a y ( i n t * arr , in t length )5
{6
int ind ;7
for ( ind = 0; ind < length ; ind ++)8
{9
i f ( arr [ ind ] == 1)10
Programming Problems Using Recursion 235
{11
printf (" %c ", ind + ’A ’);12
}13
}14
printf (" n" );15
}16
void combine Help ( in t * arr , int ind , i n t num ,17
int sel , int sum )18
{19
i f ( sum == sel ) // select enough items20
{21
printAr r ay ( arr , num ) ;22
return ;23
}24
i f ( ind == num ) // end of array , no more item to select25
{26
return ;27
}28
// select this element29
arr [ ind ] = 1;30
combin eHelp ( arr , ind + 1 , num , sel , sum + 1) ;31
// do not select this element32
arr [ ind ] = 0;33
combin eHelp ( arr , ind + 1 , num , sel , sum ) ;34
}35
void combine ( in t * arr , i n t num , in t sel )36
{37
combin eHelp ( arr , 0, num , sel , 0) ;38
}39
int main ( i n t argc , char * argv [])40
{41
i f ( argc != 3) // need two numbers42
{43
return EXIT _FAILUR E ;44
}45
int num = ( in t ) strtol ( argv [1] , NULL , 10) ;46
i f ( num <= 0)47
{48
return EXIT _FAILUR E ;49
}50
int sel = ( in t ) strtol ( argv [2] , NULL , 10) ;51
i f (( sel <= 0) || ( sel > num ) )52
{53
return EXIT _FAILUR E ;54
}55
int * arr ;56
arr = malloc ( s i z e o f ( i nt ) * num ) ;57
int ind ;58
for ( ind = 0; ind < num ; ind ++)59
{60
arr [ ind ] = 0;61
236 Intermediate C Programming
}62
combine ( arr , num , sel );63
free ( arr );64
return EXIT _SUCCES S ;65
}66
When sum equals sel, enough items have been selected and the selected items are
printed. When ind equals num, no more items are available for selection. Line 30 selects the
item and one is added to sum when recursively calling combineHelp. Line 33 “unselects” the
item and sum is unchanged in the recursive call. Either the item is selected or it is not. The
helper function recursively calls itself to determine whether to select the remaining items.
From the examples of permutations and combinations, you can see recursion is a natural
way of solving these problems. Recursion is a good approach when the solutions
have “branches”. In permutation, each element can be in one of many locations. After
setting one element to a particular location, the next element also can be in one of many
locations. By putting recursive calls inside a loop, the solution naturally solves permutations.
For combinations, each element may be selected or not and there are two branches. One
reason that makes recursion a better solution is that the number of iterations changes. For
both cases, the call stack keeps the values of the array indexes. The indexes indicate which
element to consider next. Without using recursion, programmers have to allocate memory
for keeping the values of the indexes.
15.4 Stack Sort
A stack can be used to sort a sequence of numbers, if the sequence satisfies some con-
ditions. What is a “stack”? A stack can store information based on the “first-in, last-out”
rule. The call stack is a stack that is used to control the flow of execution of a computer
program. Not every stack is a call stack. The “stack” in this section is unrelated to the call
stack described earlier. The stack sort algorithm is described as follows:
1. Create an empty stack.
2. Read one number from the sequence, call it x.
3. If the stack is empty, push the number x to the stack.
4. When the stack is not empty, we call the number at the top of the stack y.
5. If y <= x, pop y from the stack. Continue steps 4 and 5 until either the stack is empty
or top of the stack is greater x.
6. If y > x, then push x to the stack.
7. Repeat steps 2 to 6 until finishing the input sequence.
8. If the stack is not empty, then pop all remaining numbers from the stack.
9. The sequence of numbers popped from the stack is sorted if the input sequence is
“stack-sortable”. The definition is described further below.
Stack sort is a theoretically interesting algorithm, because it is fast—faster than quick
sort—but works only under particular circumstances. Those circumstances will be explained,
but first a few examples to illustrate how stack sort works.
15.4.1 Example 1
Consider the sequence <2, 1>. When 2 is read from the sequence, the stack is empty
and 2 is pushed on to the stack (step 3). Next, 1 is read from the sequence, 1 is smaller
Programming Problems Using Recursion 237
than the element on top of the stack, and is therefore pushed to the stack (step 6). Now the
sequence is finished and we pop the numbers from the stack (step 8) and the result is <1,
2>. Below is a graphical illustration of the steps. The first number, 2, is read and pushed
to the stack.
2
The second number, 1, is read and pushed to the stack.
1
2
The numbers are popped and the result is <1, 2>.
15.4.2 Example 2
The next example considers the sequence <1, 2>. The first number, 1, is read from the
sequence and pushed to the stack.
1
The second number, 2, is read. Since 1 is smaller than 2, 1 is popped from the stack and 2
is pushed on to the stack.
2
The numbers are popped and the result is <1, 2>.
15.4.3 Example 3
The third example is the sequence <1, 3, 2>. The first number, 1, is read from the
sequence and pushed on to the stack.
1
The second number, 3, is read. Since 1 is smaller than 3, 1 is popped from the stack and 3
is pushed on to the stack.
3
The third number, 2, is read. Since 2 is smaller than 3, 2 is pushed to the stack.
2
3
The numbers are popped and the result is <1, 2, 3>.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.