Home > C++ > Recursive function in C++

Recursive function in C++

In C++ recursion is the process of calling a function again & again. A function which calls itself with a shorter version of itself is a recursive function. A recursive function in c++ does the same. First, an explicit call is made to the recursive function from another function (this can be the main function or any other function). And after that, the recursive function calls itself with smaller versions of the problem. This process continues until the function reaches its stopping condition. A C++ recursive function follows the same syntax as of a function in C++. i.e.

returrnType functionName(){

functionName(); /* This will be the function call with a 
smaller version of the problem from the previous call. */

}

Most important step in using or making a recursive function is to decide when to stop making recursive calls. Because if we don’t tackle it properly, it can lead to infinite calls to the function. Hence, not returning from the function and that can lead to unexpected or undesired behavior of the program.

C++ Recursion

Let’s have a look at this function:

void myFunction(){
     …
     myFunction();
     …
}
void main(){
     …
     myFunction();
     …
}

The below figure elaborates the working of the recursive function.

recursion in c++

 

 

 

 

 

 

 

 

 

Now as stated above if we don’t have a stopping condition in our function. How and when we’ll know to stop making calls to the function by itself. The most common way to stop making infinite calls to function is the use of if-else statements. In which one block is holding the stopping condition code while the other one calls the function recursively.

Finding the factorial of a number in c++ is a very simple and common example. We can do this by simply using loops. But another efficient way of doing this is using the recursive function in c++.

Program to find the factorial of a number.

#include "stdafx.h"
#include "iostream"
using namespace std;
int factorial(int no);
int main()
{
       int n;
       cout << "Please Enter a No. to find the factorial : ";
       cin >> n;
       cout << "The Factorial of " << n << " = " << factorial(n)<<endl;
       return 0;
}
int factorial(int no) {
       // using if-else for stopping condition.
       if (no > 1 ){
              // recursive call to the function itself.
              return no * factorial(no - 1); 
       }
       else {
              return 1;
       }
}

c++ recursive function

 

 

 

 

Let’s elaborate this above-written code. We divide the above example into following steps:

1- Input from the user.

1.1- We ask the user to enter a number.

1.2- User entered 5 to find its factorial.

2- From the main function,n a call to the function named factorial is made as factorial (5).

3- The function checks if the number is greater than one than it again calls itself with a number lesser than its previous call. i.e.the function is called with number 4 as factorial (4).

4- Step 3 is repeated until the stopping condition is met.

5 – When the number is less or equal to the 1 it returns 1.

As mentioned above the most common way of stopping condition is using if-else statements. But we can use some other conditional statements as well. Let’s have a look at this example of finding the factorial of a given number.

Recursive Function using the conditional operator

#include "stdafx.h"
#include "iostream"
using namespace std;
int factorial(int no);
int main()
{
       int n;
       cout << "Please Enter a No. to find the factorial : ";
       cin >> n;
       cout << "The Factorial of " << n << " = " << factorial(n)<<endl;
       return 0;
}
int factorial(int no) {
       // using conditional operator for stopping condition.
       return (no > 1) ? no * factorial(no - 1) : 1;
}

recursive function in c++

 

 

 

 

It totally depends on the programmer to how and when to stop the calls to the function.  As both the above examples do the same thing but are using different data structure of c++.

Recursive Function using the Switch statement

Here is another variation of C++ recursive function to find the factorial of the number.

#include "stdafx.h"
#include "iostream"
using namespace std;
int factorial(int no);
int main()
{
       int n;
       cout << "Please Enter a No. to find the factorial : ";
       cin >> n;
       cout << "The Factorial of " << n << " = " << factorial(n)<<endl;
       return 0;
}
int factorial(int no) {
       // using switch for stopping condition.
       switch (no)
       {
              case 0:
              case 1:
              {
                     return 1;
              }
              default:
              {
                     return no* factorial(no - 1);
              }
       }
}

C++ recursion example

 

Sum of natural numbers using the c++ recursive function

We can write recursive functions in c++ for finding the sum of natural numbers as well.

#include "stdafx.h"
#include "iostream"
using namespace std;
int sum(int limit);
int main()
{
       int n;
       cout << "Please Enter a No. to find the sum : ";
       cin >> n;
       cout << "The Sum of natural number upto " << n << " = " << sum(n) << endl;
       return 0;
}
int sum(int no) {
       if (no == 0)
       {
              return 0;
       }
       else
       {
              return no + sum(no - 1);
       }
}

sum using recursive function

 

 

 

 

 

Just like the example above we can use other conditional statements here as well.  We can use recursive functions for performing different mathematical operations like find h.c.f and g.c.f etc.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.