A function that calls itself is known as recursive function. And, this technique is known as recursion.
void recurse() { ... .. ... recurse(); ... .. ... } int main() { ... .. ... recurse(); ... .. ... }
The figure below shows how recursion works by calling itself over and over again.
The recursion continues until some condition is met.
To prevent infinite recursion, if...else statement (or similar approach) can be used where one branch makes the recursive call and other doesn't.
// 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
Suppose the user entered 4, which is passed to the factorial()
function.
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.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.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.factorial()
function, test expression inside if statement is false. The return 1;
statement is executed, which returns 1 to third factorial()
function.factorial()
function returns 2 to the second factorial()
function.factorial()
function returns 6 to the first factorial()
function.factorial()
function returns 24 to the main()
function, which is displayed on the screen.