Basic definition of Recursion and Examples
14 November, 2016
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.
In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function. This is called recursion step. The recursion step can result in many more such recursive calls. It is important to ensure that the recursion terminates.
Example1 − a function calling itself.
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}
Example2 − a function that calls another function which in turn calls it again.
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}
Note: Both works almost same.
Importance of recursion: Recursion is a useful technique borrowed from maths. Recursive code is generally shorter and easier to write than iterative code. Generally , loops are turned into recursive functions when they are compiled or interpreted.
Notes on Recursion:
- Recursive algorithms have two types of cases, recursive cases and base cases.
- Every recursive function case must terminates at base case.
- Iterative solutions are more efficient than Recursive.
- A recursive algorithm can be implemented without recursive functions calls using a stack, but its usually more trouble than its worth. That means any problem that can be solved recursively can also be solved iteration.
Examples based on recursion:
- Tower of hanoi
- Divide and conquer Algorithms
- Dynamic Programming Examples
- Graph Traversals
- Tree Traversals
- Binary search
- Merge Sort, Quick Sort
- Fibonacci Series, Factorial Finding
- Backtracking Algorithms
