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 <int> &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.
Read more »