Recursive Algorithm

Example 1: Algorithm for computing the factorial of a given number n using Recursion.

Algorithm Factorial

//to find the factorial of n
Step1:[Accept n]
            Read n;
Step2:[call the function fact()]
            result=fact(n);
Step3:[display result]
            Write result;
Step4:[finished]
            Stop;
Algorithm fact(n)
{
            if n==0
            then
                   return 1;
            else
                   return n*fact(n-1);
}

This is the complete algorithm to find the factorial. but, I know you have a question and the question is, how does this algorithm actually work?

well, continue reading.

We all know that factorial of 0 is 1 (ie. 0!=1). For all numbers(n) greater than 0,factorial of n would be

n* factorial(n-1). The same logic, if we have to depict it in the form of a recurrence relation then, it would go as follows

lets now consider a number n to be 3 and lets apply the above algorithm fact(n) to get the factorial (3!)

As, noticed in the above example, in order to find 3! We had to call fact(n) 3 times. This is one of the few methods which produces the expected result when they are called RECURSIVELY and the algorithm associated with it is a recursive algorithm.

By now you would have got a certain idea about RECURSIVE ALGORITHMS. even more clarity you would be getting if you read the next example which is a very famous example of TOWER OF HANOI ALGORITHM USING RECURSION.

Towers of Hanoi

The Towers of Hanoi puzzle is fashioned after the ancient Tower of Brahma ritual (see Figure below).According to legend, at the time the world was created, there was a diamond tower (labeled A) with 64 golden disks.The disks were of decreasing size and were stacked on tin: tower in decreasing order of size bottom to top. Besides this tower there were two other diamond towers (labeled B and C).Since the time of creation,Brahman priests have been attempting to move the disks from tower A to tower B using tower C for intermediate storage.As the disks are very heavy, they can be moved only one at a time.In addition,at no time can a disk be on top of a smaller disk. According to legend,the world will come to an end when the priests have completed their task.

A very elegant solution results from the use of recursion.Assume that the number of disks is n. To get the largest disk to the bottom of tower B, we move the remaining n-1 disks to tower C and then move the largest to tower B.Now we are left with the task of moving the disks from tower C to tower B.To do this, we have towers A and B available. The fact that tower B has a disk on it can be ignored as the disk is larger than the disks being moved from tower C and so any disk can be placed on top of it.
The recursive nature of the solution is apparent from Algorithm below.This algorithm is invoked by Towers Of Hanoi(n,A,B,C). Observe that our solution for an n-disk problem is formulated in terms of solutions to two (n – l) – disk problem

Example: [Permutation generator] Given a set of n > 1 elements, the problem is to print all possible permutations of this set. For example, if the set is {a,b,c}, then the set of permutations is {(a,b, c), (a,c,b),(b,a,c), (b,c,a) (c,a,b),(c,b, a)}.It is easy to see that given n elements, there are n! different permutations. A simple algorithm can be obtained by looking at the case of four elements(a,b,c,d).The answer can be constructed by writing

1.a followed by all the permutations of (b,c,d)

2.b followed by all the permutations of (a,c,d)

3.c followed by all the permutations of (a,b, d)

4.d followed by all the permutations of (a,b, c)

The expression “followed by all the permutations” is the clue to recursion. It implies that we can solve the problem for a set with n elements if we have an algorithm that works on n – 1 elements. These considerations lead to Algorithm below,which is invoked by Perm(a,l,n). Try this algorithm out on sets of length one,two, and three to ensure that you understand how it works.

General Plan for Analyzing the Time Efficiency of Recursive Algorithms

1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed can vary on different inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution.