Recursion and Types2

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.