C++ Recursion

In many programming languages including C++, it is possible to call a function from a same function. This function is known as recursive function and this programming technique is known as recursion. 

To understand recursion, you should have knowledge of two important aspects:

• In recursion, a function calls itself but you shouldn't assume these two functions are same function. They are different functions although they have same name.
• Local variables: Local variables are variables defined inside a function and has scope only inside that function. In recursion, a function call itself but these two functions are different functions (You can imagine these functions are function1 and function 2. The local variables inside function1 and function2 are also different and can only be accessed within that function.

Consider this example to find factorial of a number using recursion.

Example 1: C++ Recursion

#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

Explanation: How recursion works?

Suppose user enters 4 which is passed to function factorial(). Here are the steps involved:

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