Recursive Thinking Process

Recursion is a problem‐solving approach in which the original problem is split into one or more simpler versions of itself.If the solution to the original problem involves k items, recursive thinking might split it into two problems: one involving (k − 1) items and one involving just a single item. Then the problem with (k − 1) items could be split again into one involving (k − 2) items and one involving just a single item, and so on. If the solution to all the one‐item problems is trivial then we can build up the solution to the original problem from the solutions to the simpler problems.

Let us consider a simple problem of searching an element in a sorted array via recursion. Let us consider Array A[n] where n is the size of array $$n>=0$$. We are having an element stored in the variable "target" that needs to be searched in the array A. Here instead of searching the entire array A, we use the searching mechanism on array A with $$n/2$$ elements.We compare the target value to the value of the element in the middle of the sorted array. If they are equal,then we have found the target. If not, based on the result of the comparison, we either search the elements that come before the middle one or the elements that come after the middle element. So we have replaced the problem of searching an array with n elements to one that involves searching a smaller array with only $$ n/2 $$ elements. The recursive algorithmic procedure is as follows:

RecursiveArraySearch(A[n],target)

1 if (n=0) return false
2   else if(target = A[n/2])
3        return true   
4   else if(target < A[n/2])
5        return RecursiveArraySearch(A[1...((n/2)-1)],target)
6   else if(target > A[n/2])
7        return RecursiveArraySearch(A[((n/2)+1).....n)],target)

Line 1 indicates that there are no elements to be searched and hence we can say that the target was not found. Lines 2 and 3 tell us that if the target element is equivalent to the middle element of the array then we can return that a match has been found. Lines 4 to 8 deal with the cases when the target is less than the middle element or greater than the middle element of the array A. Lines 5 and 7 call the same procedure itself with the size of the array reduced by one-half than the original call. For each recursive search, the length of the array being searched will be different, so the middle element will also be different.We will use this concept of calling the procedure or method by itself in the recursive thinking process.

Our general recursive algorithmic procedure can be described as follows:

General Recursive Algorithm

1 If the problem can be solved for the current value of n then solve it
2 else
3 Recursively apply the algorithm to one or more sub-problems involving smaller values of n
4 Combine the solutions to the smaller problems (or sub-problems) to get the solution to the original problem.

Step 1 above is called the base case : the value of n for which the problem is solved trivially. Step 3 is the recursive case because we recursively apply the algorithm. Because the value of n for each recursive case is smaller than the original value of n, each
recursive case makes progress toward the base case. Whenever a split occurs, we revisit Step 1 for each new problem to see whether it is a base case or a recursive case.

Summary of designing a recursive algorithm:

1.Recognise the base case and find a solution to it.
2.The original problem needs to be split into smaller versions of itself.
3.Every recursive case must make progress towards the base case.
4.Combine the solutions to each of the smaller problems in such a way that the original problem is solved correctly.