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)
2* 4 = 8
General Equation of recurrence Relation is
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:
- Master method
- Substitution method
- 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.