Answer to Question 17-1
When a and b are close to one another, the part to reverse
is small. If a ≥ b, the range is empty, and there is nothing to do.
Otherwise, the values in A[a] and A[b]
need to be swapped. Then reverse the ones in between,
A[a+1], … A[b−1].
Here is an illustration for a = 10 and b = 16.
The first step is to reverse the first and last values, and the
second step is the entire recursive call with a = 11 and b = 15.
|
A |
10
|
41
|
11
|
32
|
12
|
80
|
13
|
64
|
14
|
18
|
15
|
24
|
16
|
45
|
|
→
|
|
A |
10
|
45
|
11
|
32
|
12
|
80
|
13
|
64
|
14
|
18
|
15
|
24
|
16
|
41
|
|
→
|
|
A |
10
|
45
|
11
|
24
|
12
|
18
|
13
|
64
|
14
|
80
|
15
|
32
|
16
|
45
|
|
void reverse(int A[], const int a, const int b)
{
if(a < b)
{
int t = A[a];
A[a] = A[b];
A[b] = t;
reverse(A, a+1, b-1);
}
}