In the following example shows how to find the power of a number using recursion.
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.
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.