Program to find the power of a number using recursion

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)

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.