Reversing the elements of a vector using recursion

Below is an example of how to reverse the elements of a vector using recursion. This tutorial expects you to understand the following.

C++ Recursion

Example of reversing the elements of a vector

Below is an example of how one would reverse the elements of a vector by simply intuition.

// Our vector with size 5
[ X ] [ B ] [ A ] [ N ] [ Y ]
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]

//Step 1: Swap entry 0 (first) with the entry n (last)
[ Y ] [ B ] [ A ] [ N ] [ X ]
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] 

//Step 2: Swap entry 1 with entry 3 (n -1)
[ Y ] [ N ] [ A ] [ B ] [ X ]
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]

//Step 3: No swap needed for 3rd entry (or middle entry)
[ Y ] [ N ] [ A ] [ B ] [ X ]
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]

Notice how once we arrive at the entry in the middle of the vector we don’t continue. Why? The values beyond this entry have already been swapped. Keep this in mind.

Reversing the elements of a vector using iteration

Before we try making a recursive function to reverse the elements of a vector, let’s make one using iteration. By following the method described in the method above, it’s easy to see that we are simply swapping the ith and (nth – ith) variables (Example: the 0th and the 4th (4th – 0th) element).

Reversing the elements of a vector using iteration

The iterative solution for reversing the elements of a vector is below. Make sure you are trying all these functions if you haven’t before on your own.

//We pass the vector by reference
void reverseElements(vector  &vec) {

     //Temp variable for swapping
     int temp;

     int n = vec.size()-1;

     //Iterate vec.size()/2 times
     for ( int i = 0; i < vec.size()/2; i++ ) {

          // The swapping of elements
          temp = vec[i];
          vec[i] = vec[n-i];
          vec[n] = temp;

     }

     return;
}

Make sure you understand this completely before moving forward. Try working it out by hand.

Reversing the elements of a vector using recursion

So how would we start? What would the function header be?

Function header for reversing elements of a vector

So what would we need for our function header? We need the vector of course and also passed in by reference. Then we also need a way of knowing the two elements that are going to be swapped.

void revVector(vector  &vec, int lo, int hi);

// Which would be called with the following //
vector  a;

// Populate a...

revVector(a, 0, a.size()-1);

We'll name this revVector for know and the two variables to be swapped lo and hi. How are we going to use these two variables? Every new recursive calls we will increase lo and decrease hi until our base case.

So what would be our base case?

Base case for reversing elements of a vector

Your first guess might be

if ( lo == hi ) return; 

But, what if we have an even number of entries? This wouldn't be the case. Let's refine it.

if ( lo >= hi ) return; 

Now that would take care of when the vector is of even or odd size. Why? Try figuring it out if you haven't.

Below is the rest of the function.

Solution

void revVector(vector  &vec, int lo, int hi) {

     // First base case //
     if ( lo >= hi ) return;

     // The swapping
     int temp;
     temp = vec[lo];
     vec[lo] = vec[hi];
     vec[hi] = temp;

     // Next recursive call increase lo, and decrease hi by 1
     revVector(vec, lo+1, hi-1);

     return;
}

Going further

1. Can you make a helper function for this recursive function? [Hint: C++ Helper Functions]
2. Can you write a function that does the swap which would be called within your recursive/iterative version?