void transfer(int n, char start, char end, char work) {
if (n > 0) {
transfer(n-1, start, work, end);
printf("Move disk from %c to %c\n",start, end);
transfer(n-1, work, end, start);
}
}
When called for three disks, the execution profile of transfer is:
transfer(3,'A','B','C');
transfer(2,'A','C','B');
transfer(1,'A','B','C');
Move disk from A to B
Move disk from A to C
transfer(1,'B','C','A');
Move disk from B to C
Move disk A to B
transfer(2,'C','B','A');
transfer(1,'C','A','B');
Move disk from C to A
Move disk from C to B
transfer(1,'A','B','C');
Move disk from A to B
The function prints:
Move disk from A to B
Move disk from A to C
Move disk from B to C
Move disk from A to B
Move disk from C to A
Move disk from C to B
Move disk from A to B
Another example: decimal to binary
Consider the problem of printing an unsigned integer in binary. In the
very first lecture we did this by finding the largest power of two smaller
than the number and printing 0's and 1' for all the powers of two present.
We can use recursion to do this much more elegantly.
To print n in binary, print n/2 in binary and then print n%2 (the remainder
when n is divided by 2).
but this will not work for n=0, we note that the end case should be when
n=0 or n=1:
void binary(unsigned int n) {
if (n > 1)
binary(n/2);
printf("%d",n%2);
}
In this program we have replaced a 12 line iterative function by a 3 line
recursive one.
Sorting
This is one of the simplest sorting algorithms - the bubble sort. An array
is sorted by repeatedly passing through the array swapping adjacent elements
that are not in order.
Quicksort sorts an array using a recursive technique.
int n[10]={53,12,98,63,18,72,80,46,32,21};
53
12
98
63
18
72
80
46
32
21
Consider the problem of sorting the array given above
We attempt to 'partition' the elements in the array with respect to
the first element, 53 ( this element is usually referred to as the pivot).
This means that we try to put 53 in such a position that all elements to
its left are smaller and all elements to its right are larger. If this
is done, then the 53 must be in its final position in the sorted array.
For example, one method of partitioning might produce:
21
12
32
46
18
53
80
72
63
98
If we sort the portions to the left and right of 53, we will have sorted
the entire array. Sorting the original array has been reduced to sorting
two smaller arrays. To sort n[0] to n[4], we can partition this
portion with respect to the first element, 21. This puts 21 in its final
sorted position, leaving us to sort two smaller arrays. This is illustrated
by:
18
12
21
46
32
53
80
72
63
98
The portions which remain to be sorted are:
n[0] to n[1]
n[3] to n[4]
n[6] to n[9]
The process is continued until all the little pieces have been sorted.
This sort is easily written as a recursive function.
void quicksort(int n[], int left,int right) {
int dp;
if (left<right) {
dp=partition(n,left,right);
quicksort(n,left,dp-1);
quicksort(n,dp+1,right);
}
}
The function quicksort, when given two values left and right, sorts an
array from elements left to right inclusive. It calls the function 'partition'
to partition the elements with respect to some pivot. 'partition' returns
the new position of the pivot (called the division point -dp). Now we need
to write the partition function.
Assume the first element (n[left] is the pivot)
Assign pivot to the first element.
Scan from the right for an element that is smaller than pivot.
Scan from the left for an element that is larger than the pivot.
Swap these two elements.
repeat until the scans meet.
swap element at division point and n[left]
Consider the array n from earlier;
53
12
98
63
18
72
80
46
32
21
pivot=53.
scan from right for value less than or equal to 53 - 21 is found.
scan from left for a value greater than 53 - 98.
next, 21 is moved to location 2 and 98 to location 9
scanning finds 32 and 63
32 is moved to location 3 and 63 to location 8
scanning finds 46 and 72
46 is moved to location 5 and 72 to location 7
no move moves are possible and so the pivot (53) is swapped with location
5.
After this partition the array looks like this:
46
12
21
32
18
53
80
72
63
98
The following function implements the above algorithm.