Recursion

A life-saver funda which can really relieve the pain in the ass which iteration would other wise be.
Recursive function is one which calls itself again and again till a specified condition is reached.
It solves a problem by calling a copy of itself to process on a smaller problem. It is important though that the recursion would end at some condition. Otherwise, it is bound to throw stack overflow exception.
So i will be posting the recursion algos for the following scenarios where recursion is a saviour from the long long iterative algo.

• Fibonacci and factorial
• Merge sort and Quick sort
• Binary Search
• Tree traversal and Inorder, Preorder, Post Order
• Graph Traversals: DFS and BFS
• Dynamic Programming
• Divide and Conquer Algo
• Tower of Hanoi
• Backtracking algos

So for the starters here goes the recursion algo for Factorial:

int fact(n)

{

  if(n>1){

     int j = fact(n-1)

     return n*j                        //we can combine these two statements as "return n* fact(n-1)"

  }

  else if(n==1)

  {

       return 1

  }

  else

       return 1

  }

}