Finding the logarithm of a number given a base

Below is an example of how to determine the logarithm of a number of base 2 and then of any base. The logarithm of a number using a given base is power to which the base must be raised to result in the number. This tutorial assumes you understand C++ Recursion and the C++ Recursion – Power function.

Example of finding the logarithm given a base

You could find the base using two different methods.

1. Multiply the base by itself until you receive the number.
2. Divide the number by the base, and repeat until you result in 1. For this method the result is the number of computations to get to 1.

logBase2(8) = 3
2 * 2 * 2 = 8

Method 2:
8/2 = 4
4/2 = 2
2/2 = 1

logBaseN(16,2) = 4
2 * 2 * 2 * 2 = 16

Method 2:
16/2 = 8
8/2 = 4
4/2 = 2
2/2 = 1

Recursive version of logBase2 function

Given the example above, could you come up with a logBase2 recursive function? Let’s try using the 2nd method described above. So what would be our base case and header?
Read more »

Determining if a string is a Palindrome using recursion

Below is an example of how to determine if a word is a palindrome using recursion. A Palindrome is a string that could be read the same way in either direction such as racecar, mom, and even a. This tutorial expects you to understands the following.

C++ Recursion

Example of finding if a word is a palindrome

To determine if a word is a palindrome do the following.

1. Compare the first and last character
2. If these characters are the same, disregard these characters and repeat until one one character or no characters remain

Example:

// Check first and last character
[ r ] [ a ] [ c ] [ e ] [ c ] [ a ] [ r ]

// Second iteration
[ a ] [ c ] [ e ] [ c ] [ a ]

// Third iteration
[ c ] [ e ] [ c ]  

// Fourth iteration
[ e ]

// The word is a palindrome.
 

Now let’s try one that isn’t a palindrome.

// First iteration
[ t ] [ a ] [ b ] [ t ]

// In our second iteration, a and b don’t match
[ a ] [ b ]

Read more »

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 »

Greatest Common Divisor using the Euclidean Algorithm

• Introduction to Recursion in C++

Euclid’s Algorithm

When studying computer science a famous algorithm taught to students is the Euclidean Algorithm which is used to compute the greatest common divisor of two integers. It’s definition is below.

Computing various examples

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 »

Printing elements of a Vector using Recursion

• Introduction to Recursion
• C++ Recursion – Printing a Sequence of Numbers in Reverse

Iterative version for printing elements of a vector

Read more »

Creating a power function using Recursion

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

Power Function using Recursion

Let’s start by coming up with a formula again.

Taking into account negative exponents