Recursion  is a process which evaluates an object in terms of a simpler case of itself is called Recursion. The recursive algorithm invocation must eventually reduce to some computation of one or more simplest possible, non-recursive cases. Every Recursion contain the most simplest result or exit point. This scenario or condition which evaluates to simplest possible solution is known as base case. The other part of the algorithm is called as recursive case.

The recursion is a problem solving technique used by the developers when the iteration technique becomes complex to implement and reduces efficiency. There are two methodologies of developing recursive solutions, they are

1. Functional Recursion

2. Procedural Recursion

The Functional Recursion method is used where each recursive case returns a Boolean value. Finally the base case uses this Boolean value to compute the exit point if the base case was successful in resolving the simplest case, it return true. Otherwise the recursive method returns false. for e.g. Palindrome.
The Procedure Recursion method is used if the simulation of the recursive case depends on more than one variable, the base case finally evaluates the simplest possible case using these variables. The base case in this methodology usually returns the most simplest result for e.g. 1 or empty string if base case evaluates to true else it goes for next level of recursion. for e.g. Binary Search using Divide and Conquer technique.
Binary Search Algorithm using Recursion.
BinarySearch Click on the image to enlarge.
The recursive algorithm if it involves multiple functions/methods to do recursion then it is called Recursive Chain.
Following is the example which applies function recursion using recursive chain.
Recursion resolves problems which were resolved earlier using complex iterations. Recursion solutions when implemented for problems with complex iterations look very simple, direct elegant code.

All recursion simulation follow a simple pattern solution implemented recursively. Recursion is not always inefficient. Recursion should be used

  1. If we can express the simplest possible case i.e. exit point with clear, direct and elegant code.
  2. If we can logically design a task that follows recursive steps.
  3. If we can provide better solution through recursive process then any other process for e.g. iterative process.

Recursive simulation can be optimized using partial exploration technique of exhaustive recursion. For e.g. A letter combination from a given set of letters to create a new valid word found in scramble dictionary, We can apply recursive process but as the no of letters increase so the choices of selecting the letter increases as well as the depth of the decision tree increases. For every new letter added to the set of letters the depth of decision tree increases by N! and no of choices or decision taken to select a letter increase by 2 raised to N. So the recursion becomes very exhaustive. To avoid this situation we need to use the partial exploration technique of exhaustive recursion. For e.g. to compute the value of 2 raised to 10 we don’t need to recursively compute 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2, we just need to compute 2 * 2 * 2 * 2 * 2 and add it twice, in this way we have optimized the recursive code.

Recursive Backtracking Approach

There is one more recursive technique to resolve problems with complex iteration known as Recursive Backtracking. The application of recursive backtracking to a problem is as follows

– Cast problem in terms of decision points. (i.e. Choosing between different options.)

– Identify what decision needs to be made. so that decision helps in moving forward towards the resolution or the exit point.

– A recursive call makes one decision and recurs on the remaining decisions.

– Design recursion function to return success or failure.

– At each call, choose one option and go with it.

– Recursively proceed and see what happens if you can reach the base case or not.

– If it is successful then implement the required base case conclusion else if it is unsuccessful then unmake the decision and try another option.

– If no option worked, all options were exhausted to failure return failure result which triggers backtracking.(i.e. unmaking of earlier decisions).

The best examples of recursive backtracking are

1. Sudoku Game.
2. N Queens on a chess board.
3. Towers of Hanoi. Recursion Backtracking Pseudocode

bool Solve( configuration conf)


    if(no more choices)

       return configuration is the required goal.

    for(all available choices)


      try one option O;

      Solve the case if it works then mark it as done.

      Otherwise unmake the option you made for the current move


    tried all options no solution found,

    so return false.


The Subset strategy of recursion: Suppose we have N elements in a set. We need to choose k elements from that set. Then we have combination equal to C(n,k). Number of subset that include desired event/option is C(n-1,k-1). Number of subset that do not include desired event/option is C(n-1,k). Do Recursion (n , k) { if(k==0 || k==n) return 1. else return Combination C(n-1,k) + C(n-1,k-1) }

Tower of Hanoi is one of the greatest examples of Implementation of Recursive Backtracking Technique.

Digg This


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s