Algorithm

Getting Started with AlgorithmWhat is an Algorithm?

Characteristics of Algorithm1 Topic

Analysis Framework

Performance Analysis3 Topics

Mathematical Analysis2 Topics

Sorting AlgorithmSorting Algorithm10 Topics

Searching Algorithm6 Topics

Fundamental of Data StructuresStacks

Queues

Graphs

Trees

Sets

Dictionaries

Divide and ConquerGeneral Method

Binary Search

Recurrence Equation for Divide and Conquer

Finding the Maximum and Minimum

Merge Sort

Quick Sort

Stassen’s Matrix Multiplication

Advantages and Disadvantages of Divide and Conquer

Decrease and ConquerInsertion Sort

Topological Sort

Greedy MethodGeneral Method

Coin Change Problem

Knapsack Problem

Job Sequencing with Deadlines

Minimum Cost Spanning Trees2 Topics

Single Source Shortest Paths1 Topic

Optimal Tree Problem1 Topic

Transform and Conquer Approach1 Topic

Dynamic ProgrammingGeneral Method with Examples

Multistage Graphs

Transitive Closure1 Topic

All Pairs Shortest Paths6 Topics

BacktrackingGeneral Method

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Participants2253
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(n1);
}
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(n1). 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 n1 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 ndisk 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
 Decide on a parameter (or parameters) indicating an input’s size.
 Identify the algorithm’s basic operation.
 Check whether the number of times the basic operation is executed can vary on different inputs of the same size; if it can, the worstcase, averagecase, and bestcase efficiencies must be investigated separately.
 Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.
 Solve the recurrence or, at least, ascertain the order of growth of its solution.