In the following example shows how to find the power of a number using recursion.

def power(a,b):

if b==0:

return 1

elif a==0:

return 0

elif b==1:

return a

else:

return a*power(a,b-1)

print power(2,4)

if b==0:

return 1

elif a==0:

return 0

elif b==1:

return a

else:

return a*power(a,b-1)

print power(2,4)

Output: 16

Here the function 'power()' recursively called to find the power of a number.

This is the simple way to find the power of a number. But it is not a good way, that is it is not optimized. It means, suppose when the given power of a number is 100, then the function 'power()' is recursively called 99 times, also time complexity increases.

Following program shows the optimized solution for the same problem.

def power(x,y):

if y==0:

return 1

elif x==0:

return 0

elif y==1:

return x

elif y%2==0:

var_even=power(x,y/2)

return var_even*var_even

else:

var_odd=power(x,(y-1)/2)

return x*var_odd*var_odd

print power(5,10)

Output: 9765625

This is the optimized solution. Here also use the recursion, at the same time optimized recursive calls are done to find the power of a number.

That is, suppose 'n' is the power of a number 'x', and also it is an even number, then x^n=( x^n/2)*(x^n/2).

If it is in the case of odd number, x^n=x*(x^(n-1)/2)*(x^(n-1)/2). In this optimized case, the number of iterations are reduced, also we can reduce the time complexity.

## No comments:

## Post a Comment