< Browse > Home /

C++ Recursion – Greatest Common Divisor

March 7th, 2010 | No Comments | Posted in C++, Functions by Diego | - [Full Entry]

Greatest Common Divisor using the Euclidean Algorithm

Below is an example of how to create the recursive function of computing the greatest common divisor using the Euclidean Algorithm.

* This tutorial assumes you understand the following.

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.

gcd(x,y)

Computing various examples

So how does it work? Well, let’s follow the definition, but before doing that, do you remember how to compute the remainder of two integers in c++? If you don’t, well it’s the % (mod) operator.

// Computing the gcd of 45 and 9 //
gcd(45, 9)
= gcd(9, 45 % 9 ) = gcd(9, 0)
= 9

// Computing the gcd of 54 and 12 //
gcd(54, 12)
= gcd(12, 54 % 12) = gcc(12, 6)
= gcd(6, 12 % 6) = gcd(6, 0)
= 6

Read more »

C++ Recursion – Printing Elements of a Vector

February 21st, 2010 | No Comments | Posted in C++ by Diego | - [Full Entry]

Printing elements of a Vector using Recursion

Below is an example of how to print the elements of a vector using recursion. Later, we’ll print the elements in reverse. Why is this useful? You can apply this principle later to more complex data structures such as Binary Search Trees, or Linked Lists.

This tutorial assumes you understand the following:

Iterative version for printing elements of a vector

To understand how to print elements of a vector using recursion, let’s write a simple algorithm that will do it for us using iteration.

void printVector(vector <int> vec) {
   
     for ( int i = 0; i < vec.size(); i++ ) {

          //Printing ith element  followed by a space
          cout << vec[i] << " ";

     }

     //Printing end line
     cout << endl;
}

Read more »

C++ Recursion – Power Continued

February 11th, 2010 | No Comments | Posted in C++ by Diego | - [Full Entry]

Creating a power function using Recursion

So, previously we tried computing the Power function using recursion but we didn’t take into account when the exponent was negative. This continues the previous function, so if you haven’t yet, go back. Make sure you understand the following as well:

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

Power Function using Recursion

Below is our previous power function which takes into account only positive exponents. So how would we go on by taking into account negative exponents?

int power(int base, int exp) {
     
     //Return 1 when n is 0
     if ( n == 0 )
          return 1;
     else if ( n == 1 )
           return base;
     else
          return base * power(base, exp-1);
     int result = base;

}

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

power(2,-1) = (1/2);

power(2,-2) = (1/2) * power(2, -1) = (1/2) * (1/2) = (1/4);

power(2,-3) = (1/2) * power(2,-2) = (1/2) * (1/4) = (1/8);

power(2,-4) = (1/2) * power(2,-3) = (1/2) * (1/8) = (1/16);

…

//Until exp == -1
power(base, -exp) = (1/base) * power(base, exp+1);

Taking into account negative exponents

So now that we have a formula, what would be our base case? We surely don’t want our previous base case to return 1 when (n==0) because that would be wrong.
Read more »

C++ Recursion – Power

February 7th, 2010 | 1 Comment | Posted in C++ by Diego | - [Full Entry]

Creating a power function using Recursion

Below is an example of how to calculate the x to the power of n. This tutorial expects you to understand the following:

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

Example:

pow(2,3);
pow(5,4);

Result:

8
125

Iterative version of a function that calculates the power function

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

int power(int base, int exp) {

     if ( exp == 0 ) {
          return 1;
     }

     //Initial value for the result is the base
     int result = base;
     
     //Multiplies the base by itself exp number of times
     for ( int i = 1; i < exp; i++ ) {
          result = result * base;
     }

     return result;
}

Read more »

C++ Recursion – Factorial

January 26th, 2010 | No Comments | Posted in C++ by Diego | - [Full Entry]

Creating a factorial function

Below is an example of how to calculate the factorial of n. This tutorial expects you to understand the following:

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

    3. 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 »

C++ Recursion – Summation

November 13th, 2009 | 2 Comments | Posted in C++ by Diego | - [Full Entry]

Creating a sum function

Below is an example of how to calculate the total of a sequence of numbers. In this case we will be calculating the sum of 10 + 9 + … + 2 + 1

Example:

sum(10);

Result:

55

Iterative version of a function that calculates the summation

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

//Our initial total is zero
int total = 0;

//We want the sum from 1 + 2 + … + 9 + 10
int n = 10;

//The following for loop will calculate the summation from 1 – n
for ( int i = 1; i < = n; i++ ) {
     total = total + i;
}

Read more »

C++ Recursion – Printing a Sequence of Numbers in Reverse

November 6th, 2009 | 2 Comments | Posted in C++ by Diego | - [Full Entry]

Printing a sequence of numbers in reverse

Below is an example of how to reverse a sequence of numbers printed using a recursive function in C++.

10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10

Printing numbers using recursion

To understand how to print a sequence of numbers in reverse, we first demonstrate a recursive function that displays a sequence of numbers in decreasing order.

void print(int n) {
    if ( n < = 0 ) return; //Terminating condition
         
     cout << n << " "; //Prints number n

     print(n-1); //Calls itself with (n-1)

     return; //Returns from the function
}

The code above is explained in Introduction to Recursion in C++.

Example: 

 print(3);

Produces:

3 2 1

Printing Numbers in Reverse

Now, how would you print out the previous sequence of numbers but in reverse order using recursion?

Think about it. The difference from the previous question and this one is the order in which the numbers are printed. This only requires a simple modification from the previous example.

Read more »
Page 1 of 612345...Last »

Recent Post

Recommended

  • Start programming in C++

    • Most Popular within the Past Week