Question

Write a recursive function that has an argument that is an array of characters and two arguments that are the bounds (inclusive) on array indices. The function should reverse the order of those entries in the array whose indices are between the two bounds. For example, if the array is a[0]: ‘A’ a[1]: ‘B’ a[2]: ‘C’ a[3]: ‘D’ a[4]: ‘E’ and the bounds are 1 and 4, then, after the function is run the array elements should be a[0]: ‘A’ a[1]: ‘E’ a[2]: ‘D’ a[3]: ‘C’ a[4]: ‘B’ Consider the following declaration for your function: void flipArray( char arr[], unsigned int from, unsigned int to ); Test your code before writing it out. You may safely assume that from and to are valid indices with respect to arr.

Answer 1

Here is the C++ program:

#include <iostream> // for input output functions

using namespace std; // to identify objects like cin cout

/* recursive function to reverse the order of array elements between two bound of array indices */

void flipArray(char arr[], unsigned int from, unsigned int to) {

if (from >= to) // base case

return;

swap(arr[from], arr[to]);

//function to swap characters according to specified values in from and to

flipArray(arr, from + 1, to - 1); } // recursive function call

int main() { //start of main() function body

int size; //stores the number of elements in array

cout<<"Enter the size of the array: "; // prompts user to enter array size

cin>>size; // reads array size from user

char array[size]; // array of size specified by user

cout<<"Enter the characters: "; //prompts user to enter elements in array

// loop to take input characters in array according to specified size

for (int i = 0; i < size; ++i)

{cin >> array[i];} // reads array elements from user

unsigned int i,j; // stores values of two bounds of indices

cout<<"Enter the two bounds of array indices:";

// prompts user to enter two bounds of array indices

cin>>i>>j; //reads array indices from user

//displays original array elements

cout << "The original array is: "<<array<< endl;

flipArray(array,i,j); //calls flipArray() function

cout << "Array after flip from "<< i<<"to "<<j<<" is: "<<array << endl; }

/*displays elements of array after reversing array characters according to bounds of array indices */

Step-by-step explanation:

The program is explained in the given comments with every statement. Lets understand the logic of the recursive function for the input array that has characters: A B C D E and two bounds 1 and 4 i.e. from B to E

• First the base condition if (from >= to) is checked. Here the value of from is 1 and value of to is 4. So the base condition evaluates to false as 1 < 4

So the program control moves to the next statement: swap(arr[from], arr[to]); which swaps the array characters from the two indices 1 and 4.

arr [1] = B, arr [4] = E

So B and E are swapped.

A E C D B

Next statement: flipArray(arr, from + 1, to - 1); is a call to recursive function flipArray,

from + 1 = 1+1 = 2 So now the from index moves one position ahead

to - 1 = 4 - 1 = 3 So now the to index moves one position behind

So new value of from = 2 and to = 3

• The base condition is check again which evaluates to false as 2<3

The swap() function swaps the elements at indices 2 and 3 which means:

arr[2] = C

arr[3] = D

So C and D are swapped.

A E D C B

Next is the call to recursive function flipArray()

from + 1 = 2 + 1 = 3

to - 1 = 3 - 1 = 2

So the value of from = 3 and value of to = 2

• Now the base condition is checked again and it evaluates to true as 3>2

So this is the stop condition.

Hence the array after flip is:

A E D C B

The program along with its output is attached in the screen shot.