Recursion

What is Recursion? 

Any function which calls itself is called recursive. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. The recursion step can result in many more such recursive calls.

At some point, the function encounters a subtask that it can perform without calling itself. This case, where the function does not recur, is called the base case. The former, where the function calls itself to perform a subtask, is referred to as the recursive case.

Why Recursion?
Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter and easier to write than iterative code. Generally,

Recursion is most useful for tasks that can be defined in terms of similar subtasks.

Recursion and Memory (Visualization)

Each recursive call makes a new copy of that method (actually only the variables) in memory. Once a method ends (that is, returns some data), the copy of that returning method is removed from memory.

Code

Memory visualization

Example Algorithms of Recursion 

• Fibonacci Series, Factorial Finding 
• Merge Sort, Quick Sort •Binary Search 
• Tree Traversals and many Tree Problems: InOrder, PreOrder PostOrder 
• Graph Traversals: DFS [Depth First Search] and BFS [Breadth First Search] 
• Dynamic Programming Examples 
• Divide and Conquer Algorithms 
• Towers of Hanoi

Problems

• Factorial Recursive function - 1.Factorial.cpp
• To Check whether array in sorted order using recursion - 3.Problem3.cpp