Critical Review
Topic-Recursion
“To understand recursion, one must first understand Recursion.”
-Stephen Hawking
BASIC-
Something is said to be of recursive nature if it forms smaller and similar instances form part of its whole.
For example A tree stem is the whole part and it is furthermore divided into branches, those branches are further divided into small branches which comes stop when they find a bud, flower, leaf or fruit.
Tree Branches
Or for an instance breaking of a molecule until an atom is found.
In general during solving a recursive problem the first step is to always think of the base condition while the main challenge is to design the recursive structure of a problem.
Breaking of complex problems into simpler and more readable ones is known as decomposition .
When a problem occurs of recursive nature first of all think how you can decompose it into further more simpler problems.In order to write recursive algorithm it is very important to decompose problem into smaller self-similar subproblem and define the method on induction.
Decomposition has already been discussed above, Induction is also known as recursive leap of faith where the programmer already believes that this recursive Algorithm will definitely work for smaller sub problem.
Recursion comes under the declarative paradigm of programming which is strongly based on what a certain function accomplish instead how they do it? Therefore every Programmer while writing a recursive function should view it from the hight level instead of going in deep of the recursive calls.
ITERATION Vs RECURSION
Every iterative program can be converted into a recursive and vice-versa. But in imperative programming iteration is preferred while in functional programming recursion is preferred.
Recursion occupies extra space on the program stack and sometimes can even cause stack overflow. It is also slower than iterative function and recursive codes are hard to debug.
Types of Recursion
1-Linear Recursion- When method calls themselves only once.
2-Tail Recursion-In this also method calls only once but the recursive call is the last operation.
3-Multiple Recursion-When a method calls itself several times.
4-Mutual Recursion-When methods can call itself in a cyclic order.
5-Nested Recursion-When an argument of a recursive function is defined through another recursive call.
Steps for designing any recursive algorithm-
1-Analyse the size of the problem.
2-Write the base case.
3-divide it into self-similar subproblem.
4-Define recursive structure based on Induction.
Methodology for Recursive thinking-
When thinking recursively we generally don’t have to think of the smallest subproblem as that leads to confusion.
Recurrence Relation-
The running time or number of operations carried out by an a recursive Algorithm is specified through a recurrence relation.
Linear Recursion-
This is the simplest type of recursion.The classical problem used to illustrate recursion is the power function for example-
Here in the above given example we need to find the the value of b**n function.
according to the methodology explained earlier the first step is to find the size of the function which by clearly looking at it depends on n.The next step is to find the base case, so the base case is our smallest instance of our bigger subproblem which will be b**0 which is 1.
Now in the decomposition step we have to think of the smaller self similar subproblem that comes from reducing the size of the problem in this problem we will simply decrement it by single unit then our function will become b**(n-1).
Therefore this is an example of linear recursion since there is only one recursive case to call each time.
For example-
Is a string Palindrome ?
E.g “radar”
There are two base cases here (i) When the string is empty and (ii) When there is only single character in the string in both the situations the output will be True.
The recursive structure would be that “ada” is a palindrome that is if his the first character and l is the last character f+1 to l-1 each time while calling the function.
Tail Recursion-It is also known as the final kind of recursion in which the recursive function invokes the method once. In the linear recursion all the problems were based on decreasing the size of problem by one or two unit but here in this type we will more focus on dividing the problem in half.
Multiple Recursion-
The advantages of recursion over iteration such as code clarity or avoiding managing stack explicitly is because of the possibility of using the multiple recursion.In this type of recursion we divide the problem’s size by constant.
For example merge sort use divide and conquer approach.
For example- Here the array has been divided into two sub-self similar arrays which divides themselves further into self similar arrays until the single element is reached that is our smallest instance. When the base case is reached the function backtracks thus evaluating the value.
There is another very renowned problem based on multiple recursion “Tower of Hanoi”
TOWERS OF HANOI
It is one of the most renowned problem and widely used to illustrate recursion.The game consists of three vertical rods.The goal is to move the entire tower of stacked disks from initial rod to final rod with the help of third rod by obeying the following ruled
1-Only one disk can be moved at a time.
2-A larger disk cannot be placed on smaller disk.
3- Each move takes the upper disk staked placed on top of one of the rods and place it on top of the other rod.
The size of the problem is defined by the number of disks. The base case occurs when the disk is 2*n-1.Therefore for n=4 the number of moves required would be 15.
Although the number of moves increases exponentially as n grows, the difficulty of the problem is essentially the same as the case for n = 2 if we apply recursion. The most interesting configurations of disks in the solution for n = 4 are the ones after moves 7 and 8. Observe that after the seventh move there are n − 1 disks on the auxiliary rod. This situation is necessary in order to move the largest disk onto the destination rod. Thus, the first seven steps consist of solving the puzzle for n − 1 = 3 disks, where the goal consists of moving them from the origin to the auxiliary rod, with the help of the destination rod. In other words, the roles of the destination and auxiliary rods are switched. The eighth move is just a basic operation that involves moving the largest disk. After it is placed on the destination rod, there is a stack of n − 1 disks on the auxiliary rod that needs to be moved onto the destination rod. Therefore, the seven remaining steps consist of solving another problem of n − 1 disks, where in this case the roles of the auxiliary and origin rods are switched. This reasoning based on problem decomposition and induction is illustrated in Figure 7.6. In particular, the decomposition considers two problems of size n−1, where the solution consists of three operations. The first and third steps solve one of these subproblems, while the second operation simply moves the largest disk onto the destination rod. A recursive solution can therefore rely on induction in order to assume that we can move entire stacks of n − 1 disks in a single step (which corresponds to a recursive call). In that case note that the solution is conceptually very similar to the one for n = 2. In particular, observe the similarity between Figures 7.4 and 7.6. Both solutions consist of three steps, where disk 1 is replaced by a full stack of n − 1 disks in Figure 7.6 (and disk 2 plays the same role as disk n).
Counting Problems
Recursion is used extensively in combinatorics, which is a sub field of mathematics that studies counting and plays an important role in advanced mathematics.
Backtracking-
It is one of the most important Algorithm design paradigm which is also regarded as intelligent brute-force strategy. The approach can be used to solve many puzzles and problems for example eight-queens problem,0–1 knapsack, finding path through maze.
Backtracking methods are generally combine recursion and iteration, they are not often designed thinking about decomposition and induction.
At last I would like to conclude with, I believe that recursion is easy only we make it complicated.
