Back to Course


0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 5, Topic 1
In Progress

Recursive Algorithm

Lesson Progress
0% Complete
KodNest algo1

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()]
Step3:[display result]
            Write result;
Algorithm fact(n)
            if n==0
                   return 1;
                   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

KodNest algo2
KodNest Recursion3

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

KodNest Recursion4
KodNest Recursion5
KodNest Recursion6
KodNest Recursion7

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.

KodNest Capture20
Fig: Towers of Hanoi

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

KodNest Capture21
Algorithm: Towers of Hanoi

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.

KodNest Capture22
Algorithm: Recursive permutation generator

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.

New Report