Recursive Algorithm

Hey Guys !!! Welcome back to the Algorithm shelf .Today we will see the types of algorithm. As this part is very vast so ,I have included only one type in brief. So let’s begin with the fundamentals.

An algorithm is a set of self contained sequence of instructions or actions that contains finite space or sequence and that will give us a result to a specific problem in a finite amount of time.

Simply we can define as , a logical and mathematical approach to solve or crack a problem using any possible method.

Algorithm is divided into a finite number of types and some of them which is generally used are given in above figure.

1.Recursive algorithms: 

As we are familiar with the concept of recursive function i.e. The function which call itself again and again within  the same function until the given condition is not satisfied that is called a Recursive function.

 similarly, an algorithm is said to be recursive if the same algorithm is invoked in the same body. That is ; one which calls again and again within the same body is known as Recursive algorithm.     

This recursive mechanism is extremely powerful cause many times it express the complex problems clearly that’s why recursive is introduce as an kind of algorithm where it is also called as the direct recursive algorithm.

Suppose the algorithm A calls another algorithm which in turns calls A then it said to be indirect algorithm.

Typically the beginners have the view as recursive mechanism is some how mystical technique which is used for only some special case problems.

But this is very unfortunate because the any algorithm that is written by using a statements like if-then-else statement, while statement can write by using recursive mechanism. Of course the results may have some difficult step’s to understand.

The example given below can explain the Recursive algorithm smoothly:

Example 1: Tower of Hanoi. [1. Move one disk at a time. 2. No time can a disk be on top of a smaller disk. ]

    The tower of Hanoi is a puzzle discovered after the ancient Tower of Brahma ritual.

Confused ? . . . OK I’ll explain with very simple steps. So let’s consider we have three disks i.e. Red,White,Green and three towers i.e. A,B,C . All disks are arranged in order such as largest disk is at the bottom of the Tower as shown in first figure.

6.I think after this step solution is clear to all of you. 7.Now we have to just put the White, Red disk in Tower C respectively.

1. Algorithm TowerOfHanoi( n, x, y, z )
2. // move the top n disks from tower x to tower y.
3. {
4. if ( n > = 1 ) then
5. {
6. TowerOfHanoi ( n – 1, x, z, y )
7. write( ” move top disk from tower “, x, “to top of tower”, y );
8. TowerOfHanoi ( n – 1, z, y, x );
9. }
10. }

Example 2: Recursive Algorithm for Sequential Search

Algorithm:   SeqSearch(L, i, j, x)
Input:L is an array, i and j are positive integers, i<=j, and x is the key to be searched for in L.
Output: If x is in L between indexes i and j, then output its index, else output 0.

1. Algorithm SeqSearch(L, i, j, x)
2. {
3. ifi<=j ,then
4. {
5. if L(i) = x, then return i ;
6. else return SeqSearch(L, i+1, j, x)
7. }
8. else return 0.
9. }
10. // Recursive algorithms can also be used to test objects for membership in a set.

Hope Recursive algorithm is well understood by you all guys . Stay tuned for knowing the next type . Please do write all your queries in comment box.Thank you…