Answer:
p(x,n)
1. if(n==0) [if power is 0]
2. then result =1.
3.else
4. { result=1.
5. for i=1 to n.
6. { result = result * x. } [each time we multiply x once]
7. return result.
8. }
Let's count p(3,3)
30, so come to else part.
i=1: result = result *3 = 3
i=2: result = result *3 = 9
i=2: result = result *3 = 27
Explanation:
here the for loop at step 4 takes O(n) time and other steps take constant time. So overall time complexity = O(n)
Answer:
No you can not tell that recursion is ever required to solve a problem.
Recursion is required when in the problem, the solution of the input depends on the solution of the subsets of the input.
Iteration is also another form of repetitive approach we follow to solve that kind of problems.
But the difference between recursion and iteration is :
Explanation:
For example in the Fibonacci sequence problem, to find , we need to compute
and
before that.
Fibonacci(n)
1. if(n==0 or n==1)
2. return 1.
3.else
4. return( Fibonacci(n-1)+Fibonacci(n-1) )
Fibonacci(n)
1. if(n<=2)
2. result = 1
3. else
4. result1 =1 and result2=1.
5. { result = result1 +result2.
6. result1= result2.
7. result2 = result.
8. }
9. output result.