Recursion & Recursive Functions in C++

In this Tutorial we will understand the concept of Recursion and Recursive Functions in C++. If you don’t know what Functions are in C++ Check This Out

A Recursive Function is a Function which calls itself. This mechanism is known as Recursion. Recursive functions are generally used in algorithms based on divide and conquer techniques and where there are certain number of iterations to be performed to reach the final output.

Recursive functions in c++Recursion & Recursive Functions in C++ diagram

The recursion continues until some condition is met to prevent it. To prevent infinite recursion, if…else statement (or similar approach) can be used where one branch makes the recursive call and other doesn’t.

Recursive Functions in C++ Example Program

Run Online

// Factorial of n = 1*2*3*...*n
#include <iostream>
using namespace std;

int factorial(int);
int main() 
{
    int n;
    cout<<"Enter a number to find factorial: ";
    cin >> n;
    cout << "Factorial of " << n <<" = " << factorial(n);
    return 0;
}

int factorial(int n) 
{
    if (n > 1) 
    {
        return n*factorial(n-1);
    }
    else 
    {
        return 1;
    }
}
Output
Enter a number to find factorial: 4
Factorial of 4 = 24
Program Explanation

Suppose the user entered 4, which is passed to the factorial() function.

  • In the first factorial() function, test expression inside if statement is true. The return num*factorial(num-1); statement is executed, which calls the second factorial() function and argument passed is num-1 which is 3.
  • In the second factorial() function, test expression inside if statement is true. The return num*factorial(num-1); statement is executed, which calls the third factorial() function and argument passed is num-1 which is 2.
  • In the third factorial() function, test expression inside if statement is true. The return num*factorial(num-1); statement is executed, which calls the fourth factorial() function and argument passed is num-1 which is 1.
  • In the fourth factorial() function, test expression inside if statement is false. The return 1; statement is executed, which returns 1 to third factorial() function.
  • The third factorial() function returns 2 to the second factorial() function.
  • The second factorial() function returns 6 to the first factorial() function.
  • Finally, the first factorial() function returns 24 to the main() function, which is displayed on the screen.
Watch it on YouTube

Leave a Reply

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