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 »

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 »

Overview of Tail Recursion

Tail Recursion is simply a special form of recursion, in which the recursive call is at the end of the function. This allows for improved efficiency as the final value to be computed is returned without any further calculation when the recursion function terminates.

Factorial without Tail Recursion in C++

First a version without tail recursion will be shown in C++. This version requires that the function has to compute a new value to return to it’s caller after the function it called returned a value.

Factorial with Tail Recursion in C++

Below is the factorial function with tail recursion. Can you tell the difference from the one posted above? The function below doesn’t need to do any more computations when the function it called returns (considering its not the last function that was called). It simply returns the value without any further calculation.

Usually, if it can be done using tail recursion, the function can be iteratively solved as well.

Tail Recursion in a functional language

In C++, if you can write a tail recursive function most likely you can right an iterative version. In a functional language where iteration isn't possible, tail recursion allows for greater efficiency in such functions.

Read more »

Overview

A helper function is merely a function that passes additional arguments to another function of a similar name. The additional arguments that are passed in are usually predetermined by the programmer that allow the use of recursion.

This tutorial considers you are knowledgeable with recursion since our example deals with a recursive function.

Example of a helper function

Below we’ll provide you an example of when you might encounter the use of a helper function. We’ll start off by introducing a simple print function that prints all the elements of a vector.

This function would be called in your main program in the following way.

Where the helper function comes in

Now, imagine for some reason you want to try making your print function recursively. The thing is, if you want to print using recursion, you need your function to have an additional parameter in order to track what element we are currently printing.
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 »