RSS

Beginner Level C++ Recursion Examples

01 Dec

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 will be explained later.

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.

Hint: Try moving your printing statement around your function.

 

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


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;
}

Using Recursion


So how would we go by solving this using recursion? First of all we need a function header.

int sum(int n)

Next, if you remember from the basics of recursion, our function needs a base case orterminating condition. What would it be in this case? When we are trying to sum the sequence consisting of only 0. We also don’t want to calculate the summation of negative numbers.

int sum(int n) { 

     //Return 0 when n is 0
     if ( n <= 0 ) return 0;
}

Now, how would go on by computing the sum using recursion? Let’s start by drawing a diagram on how this could be done.

summation

From the drawing above, we calculate the sum of 1 by adding 1 to the sum of 0, which is ourterminating condition, which is 0.

Translating the following formula into code, is then fairly trivial. This would allow us to apply our summation formula to any positive integer.

int sum(int n) { 

     //Return 0 when n is 0
     if ( n <= 0 ) return 0;
     else
          return n + sum(n-1);

}

The previous recursive function will work as follows (in our case, sum(3)).

summation2]

 

 

 

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


    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;
    }

    Recursive Version


    So how would we go by solving this using recursion? First of all we need a function header.

    int factorial(int n)

    Next, what would be our base case? When we are trying to calculate the factorial for 0, the result should be 1.

    int factorial(int n) {
    
         //Return 1 when n is 0
         if ( n == 0 ) return 1;
    }

    Now, how would we go on by computing the factorial using recursion? Let’s come up with a formula by calculating the factorial of 2,3, and 4.

    factorial(1) = 1;
    
    factorial(2) = 2 * factorial (1) = 2 * 1 = 2;
    
    factorial(3) = 3 * factorial (2) = 3 * 2 = 6;
    
    factorial(4) = 4 * factorial (3) = 4 * 6 = 24; 
    
    ...
    
    factorial(n) = n * factorial(n-1);

    Translating the above formula to code, is then fairly trivial. This would allow us to apply our factorial formula to any positive integer.

    int factorial(int n) {
    
         //Return 1 when n is 0
         if ( n == 0 ) return 1;
    
         //factorial(n) = n * factorial(n-1);
         return n * factorial(n-1);
    }

 

About these ads
 
7 Comments

Posted by on December 1, 2010 in C++ Programming, Uncategorized

 

7 responses to “Beginner Level C++ Recursion Examples

  1. narnia

    December 10, 2010 at 8:47 PM

    loving this blog more and more every day

     
  2. muhammad imran

    June 27, 2013 at 12:52 PM

    it not enough information

     
    • prasanth

      June 27, 2013 at 1:13 PM

      please let me know what kind of more info you require and i will gladly help you out.

       
  3. Aditya

    January 18, 2014 at 8:53 PM

    in the factorial program using recursive function,the final output should always should be 1 since its returns 1 when the number becomes zero in any case but why it is not so?

     
    • prasanth

      January 18, 2014 at 10:21 PM

      It goes like this : if we are calculating factorial(3), the function output will be 3 * factorial(2), whose return value is 2 * factorial(1), which returns 1 * factorial(0), which returns 1. hence the final output is 3 * 2 * 1 * 1. Hence as you can see, the return value for the final function is always 1, but there are other multiplications before that function that takes place that gives us the required factorial value.

       
      • Aditya

        January 18, 2014 at 10:34 PM

        thank you :)

         

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: