## DESIGN AND ANALYSIS OF ALGORITHM

It's all about self learning.

Recursion versus Iteration and Types of Recursion
15 November, 2016

Recursion Versus Iteration: When we are working on both Recursion and Iteration , which way is better??

Iteration or Recursion??

Some time it depends what kind of problems we are facing . Generally, a recursive approach mirrors the problem that we are trying to solve . A recursive approach makes it simpler to solve a problem which may not have the most obvious of answers. But recursion adds overhead for each recursive call.

Eg)  Write a recurrence relation to perform exponential operation  between given two non zero positive numbers
Ans:  pow(2,3) = 2 * pow(2,2)

2 * pow(2,1)
2 * pow(2,0)  this is termination

Result is 8. How??

Exp:  start from the termination 2* pow(2,0)

2*1= 2 because pow(2,0)=1

Now 2 * pow(2,1)
pow(2,1)=2*pow(2,0)=2

So 2*2=4
Finally 2*pow(2,2)
2* 4 = 8

General Equation of recurrence Relation is

Recurrences relation=

pow(a,b =       0    if  a=0

1    if b=0

a* pow(a, b-1)   if a> 0 and b>0

General Representation of recursion:

fact(n) = 1 if n=0;

n* fact(n-1)  n>0

Solving Recurrence Relation:

1. Master method
2. Substitution method
3. Recursive Tree Both types will give the same complexity but the solving method is different.

In the next chapter , we will continue with substitution examples and 3rd type Recursive call. 