# Recursion in C++ program

Document Contents

### Overview

Recursive function is a function that invokes itself. In this post, we will discuss recursion and a sample C++ program that uses a recursive function.

### Sample program

```/**************************************
* Recursive function demo C++ program
****************************************/
#include <iostream>
using namespace std;

//Function prototype
int Factorial(int);

// main Function
int main(){
int n;
cout << "Enter n" << endl;
cin >> n;
cout << n << " factorial is = " << Factorial(n) << endl;
return 0;
}

/**********************************
* Recursive function to calculate
* factorial of n
* Mathematical formula=
* n! = n*(n-1)!
***********************************/
int Factorial(int n){
if(n == 0)
return 1;
else
return n* Factorial(n-1);
}
```

### Sample output

Enter n
6
6 factorial is = 720

Process returned 0 (0x0) execution time : 15.781 s
Press any key to continue.

——————————

Recursive function usually has:

a recursive call to the function itself.
termination that stops the recursion.

Mathematical representation of the factorial is:

n! = {    1  for n=0

n*(n-1)!  for n>= 1

For example, the termination part of the program:
if(n==0)
return 1;

We know that 1! = 1. The recursion stops when n becomes 1.

To understand how recursion in the above program works, lets visualize what happens when the function calls itself.

Recursive calls for the Factorial(6) is as follows

Factorial(6) = 6* Factorial(5)

= 6* 5* Factorial(4)

. .  .

= 6*5*4*3*2*Factorial(1)

Termination part Factorial(1) = 1