It's all about self learning.

Recursion and Types

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)

               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)
                         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

Multiple Choice Questions