Introduction

Recursion is a way of solving the given problem via solving the smaller versions of the same problem. It is a widely used programming paradigm to solve complex problems by breaking down to the smaller sub problems.

Recursion is used mainly in divide-and-conquer approach in which the given problem is divided into smaller problems until the sub problems become simple enough to be solved directly and the solutions of the sub problems are then combined to get the solution of the actual problem.

Recursion Using a Game

To understand recursion easily lets try to solve a small game.

Problem Statement

1Problem Description :  
2You are given n objects whose weight is unknown and you are given a double pan balance which is allowed to compare only two objects at a time. There is no way to find the weight of the individual object. You need to find out the heaver object among the all given objects. 
3
4Input: n Objects whose weight is unknown and a double pan balance 
5 
6Output: Heavier object among n objects 

Game Rules

• Weights of the objects are unknown
• We can use double pan balance to compare only two objects at a time.
• There is no way to calculate the weight of the individual object.

Solution Approach

Lets solve the given problem by taking an example in which we are given 8 objects which are o1, o2, o3, o4, o5, o6, o7 and o8.

• As we are able to compare only two objects at a time, we can divide the given objects into two parts of equal in size. As n is 8, we get two sets contains 4 objects each. Then set1 contains o1, o2, o3, o4 and set2 contains o5, o6, o7, o8.
• Again divide both sets set1 and set2 further. Then we get 4 sets which are {o1, o2}, {o3, o4}, {o5, o6} and {o7, o8}

• Now we arrived into situation that each set contains two objects each and we are able to compare now.

• Solve each set which contains 2 objects each by using double pan balance and lets assume we got the heavier objects as below :

  • for set {o1, o2} -> o1
  • for set {o3, o4} -> o4
  • for set {o5, o6} -> o6
  • for set {o7, o8} -> o7

• Now compare the solutions of the above subsets by taking 2 at a time and compare using double pan balance as below :

  • for set {o1, o2} -> o1
  • for o6, o7 -> o7

• Finally compare o1 and o7 and we got o7 as the heavier object .

So o7 is heavier object of given objects {o1, o2, o3, o4, o5, o6, o7, o8}

Recursion Rules

If we notice the solution approach of the above problem, we have broken down the problem into sub problems and again each sub problem breaks down into further smaller sub problems and we stopped this when the smaller problem has only two objects to compare. This is called base case. Here every sub problem looks exactly the same as the given problem, just changing the number of objects. This is called Recursive Relation. Every recursive algorithm must satisfy these rules which are given below :

• Recursive algorithm must have a base case
• Recursive algorithm must change its state, and has to move towards its base case
• Recursive algorithm must call itself, recursively.

Recursive Algorithms

• Binary Search
• Merge Sort
• Quick Sort
• Tree traversal Algorithms

Merge Sort and Quick Sort algorithms uses Divide-and-Conquer approach in which the given problem breaks down into sub problems that are similar to the original problem, recursively solves the sub problems, and finally combines the solutions to the sub problems to solve the original problem.

In this post we have explained recursion approach using small game, where objects weight is unknown. To write code lets convert the game into problem of finding max element in the given array and the problem is explained in divide-and-conquer approach.

Note : The example which we discussed here recursion is used along with divide-and-conquer approach. But It is not the case always. Like if we solve binary search using recursion we are going to divide the problem into 2 sets and we ignore one set and continue the search process in other set.