Analysis of Algorithm Recursive Algorithm

Recursive Algorithm

1. 1


1.1Algorithm Definition and Specification
1.2 Space complexity
1.3Time Complexity
1.4 Asymptotic Notations
1.5 Elementary Data Structure:
Stacks and Queues
1.6 Binary Tree
1.7 Binary Search Tree
1.8 Heap
1.9 Heapsort
1.10 Graph.
UNIT 1- INTRODUCTION

2. Recursive Algorithm
2
A recursive function is a function that is defined in
terms of itself. Similarly, an algorithm is said to be
recursive if the same algorithm is invoked in the body. An
algorithm that calls itself is direct recursive. Algorithm A
is said to be indirect recursive if it calls another algorithm
which in turn calls A. These Recursive mechanisms are
extremely powerful, but even more importantly,

3. 3
Fact(n)
{
if n == 0 or 1 then
Return 1;
else
Return (n*Fact(n-1));
}
Contd…
Example1 : Factorial using Recursion
Implementation
Fact(3)
{
if n == 0 or 1 then
Return 1;
else
Return (3*Fact(2));
}
Result=6
Fact(2)
{
if n == 0 or 1 then
Return 1;
else
Return (2*Fact(1));
}
Result=2

4. 4
Fact(1)
{
if n == 0 or 1 then
Return 1;
else
Return (1*Fact(0));
}
Result=1
Notation

5. 5

Contd…
Example2 : Towers of Hanoi using Recursion
There are three towers
64 gold disks, with decreasing sizes, placed on the
first tower
You need to move all of the disks from the first
tower to the last tower
Larger disks can not be placed on top of smaller
disks
The third tower can be used to temporarily hold
disks

6. 6
The disks must be moved within one week.
Assume one disk can be moved in 1 second.
Is this possible?
To create an algorithm to solve this
problem, it is convenient to generalize the
problem to the “N-disk” problem, where in
our case N = 64.

7. Recursive Solution
Tower A Tower B Tower C

8. Recursive Solution
Tower A Tower B Tower C

9. Tower of Hanoi

10. Tower of Hanoi

11. Tower of Hanoi

12. Tower of Hanoi

13. Tower of Hanoi

14. Tower of Hanoi

15. Tower of Hanoi

16. Tower of Hanoi

17. Algorithm –Towers of Hanai
17