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 »

The Fibonacci Sequence

• Introduction to Recursion in C++

Fibonacci is a well known number sequence that models the growth of a rabbit population amongst other things found in nature.

Below is the Fibonacci numbers computed up to the 11th term.

Iterative version of Fibonacci

Fibonacci Formula

Fibonacci(0) = 0;
Fibonacci(1) = 1;
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2);

So how would we do an iterative version? I’ll walk you through the code.

So how would we compute the value of the nth value of the Fibonacci sequence? We can do it with a for loop, to add UP to the value we are looking for. In other words, if we were doing it by hand, we’d do it as following:
Read more »

Creating a factorial function

1. C++ Recursion
2. C++ Recursion – Summation

Example:

factorial(5);

Result:

120

Iterative version of a function that calculates the factorial

---

To understand how to calculate the factorial using recursion, let’s write a simple algorithm that will do it for us using iteration.

int factorial(int n) {

     //Initial value for the final value is 1
     int factorial = 1;
     
     for ( int i = 2; i < = n; i++ ) {
          factorial = factorial * n;
     }

     return factorial;
}

Read more »

Creating a sum function

Example:

sum(10);

Result:

55

Iterative version of a function that calculates the summation

Read more »

Recursion in C++ is simply a function that calls itself that terminates when a base case is met. It’s very useful to learn how recursion for a couple of reasons.

• It’s easier to solve certain problems with recursion as the resulting code is usually shorter
• Sometimes its the only way

Displaying numbers recursively

So what’s an example of a recursive function? Let’s make one. Let’s start by creating a function that displays a number (it isn’t the best example, but it’s good enough to introduce you to recursion).

Display Function

All this function does is simply print the number passed in.

Recursive Display Function

Now let’s have this function call itself but lets decrement the value being displayed each time.

So let's say we executed display(10)

What would this display? It would display 10 9 8 7 6 5 4...and would never stop. Why? We never told the function when to terminate. This will either cause your program to run until you kill it, or may cause it to segmentation fault. In order to fix this, this calls for the addition of base case. Read more »

Fibonacci is a well known number sequence that models the growth of a rabbit population amongst other things found in nature.

The Fibonacci Numbers Sequence

Below is the Fibonacci numbers computed up to the 11th term.

The formula for Fibonacci

Computing for Fibonacci is simple. The formula is below.

Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2);

To computer for Fibonacci of 7, simply add the values of Fibonacci of 6 and Fibonacci of 5. In other words, the sum of the previous two values.

Fibonacci(7) = Fibonacci(6) + Fibonacci(5);
Fibonacci(7) = 8 + 5;
Fibonacci(7) = 13;

Iterative version of Fibonacci

This is an iterative version of Fibonacci.

Read more »