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
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
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
- 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 worst-case, average-case, and best-case 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.