How to write recursive function

What is Recursive Function?

Function that calls itself is called as Recursive Function. A Recursive Function is basically used to solve a problem by solving smaller subproblems of original problem. 

Remember every Recursive function should have a termination condition, else your function will run infinitely.

Let's consider a simple problem. Suppose you want to add numbers upto n. Your first solution will be -

f(n) = 1 + 2 + 3 +……..+ n

But if you want to do it via Recursion, your code will be become -

If f(n) = 1
    return   n=1

Else f(n) = n + f(n-1)
    return  n>1

Another simple recursive example can be finding factorial of a number.

int fact(int n) { 
    if (n < = 1) // base case 
         return 1; 
    else 
         return n*fact(n-1); 
}

C++ Recursive Code for Finding Factorial of number -

# include<iostream>
using namespace std;

int factorial(int n){
    if (n<=1){ // termination condition
        return 1;
    }
    return n * factorial(n-1);
}



// Step by step calculation of factorial(4)

// factorial(4) = 4 * factorial(3); 

// factorial(4) = 4 * 3 * factorial(2);

// factorial(4) = 4 * 3 * 2 * factorial(1);

// factorial(4) = 4 * 3 * 2 * 1;

// factorial(4) = 24;


int main(){

    // Factorial of a number. Ex:
    // 6! = 6*5*4*3*2*1 = 720
    // 0! = 1 by definition
    // 1! = 1 by definition
    // n! = n * (n-1)!
    int a;
    cout<<"Enter a number"<<endl;
    cin>>a;
    cout<<"The factorial of "<<a<< " is "<<factorial(a)<<endl;
    return 0;

}