Answer to Question 16A-2
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.
If a = b, there is just one thing, and again
there is nothing to do.
If a < b, the values in A[a] and A[b]
need to be swapped. Then reverse the values in between,
A[a+1], … A[b−1].
Here is an illustration for a = 10 and b = 16.
The first step is to swap 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
|
80
|
|
13
|
64
|
|
14
|
18
|
|
15
|
32
|
|
16
|
45
|
|
→
|
|
A |
|
10
|
45
|
|
11
|
24
|
|
12
|
18
|
|
13
|
64
|
|
14
|
80
|
|
15
|
32
|
|
16
|
45
|
|
Here is a definition of reverse using those ideas.
void reverse(int A[], int a, int b)
{
if(a < b)
{
int t = A[a];
A[a] = A[b];
A[b] = t;
reverse(A, a+1, b-1);
}
}