Answer to question 16-1

Answer to Question 16-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. If a = b−1, there is just one cell, and again there is nothing to do.

Otherwise, 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 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

Here is a definition of reverse using those ideas.

  void reverse(int A[], const int a, const int b)
  {
     if(a < b - 1)
     {
       int t = A[a];
       A[a] = A[b];
       A[b] = t;
       reverse(A, a+1, b-1);
     }
  }