Given a number N and power P, the task is to find the power of a number ( i.e. NP ) using recursion.
Examples:
Input: N = 2 , P = 3
Output: 8Input: N = 5 , P = 2
Output: 25
Approach: Below is the idea to solve the above problem:
The idea is to calculate power of a number ‘N’ is to multiply that number ‘P’ times.
Follow the below steps to Implement the idea:
- Create a recursive function with parameters number N and power P.
- If P = 0 return 1.
- Else return N times result of the recursive call for N and P-1.
Below is the implementation of the above approach.
Python3
# Python3 code to recursively find# the power of a number# Recursive function to find N^P.def power(N, P): # If power is 0 then return 1 # if condition is true # only then it will enter it, # otherwise not if P == 0: return 1 # Recurrence relation return (N*power(N, P-1))# Driver codeif __name__ == '__main__': N = 5 P = 2 print(power(N, P)) |
25
Time Complexity: O(P), For P recursive calls.
Auxiliary Space: O(P), For recursion call stack.
Optimized Approach :
Calling the recursive function for (n, p) -> (n, p-1) -> (n, p-2) -> … -> (n, 0) taking P recursive calls. In the optimized approach the idea is to
decrease the number of functions from p to log p.
Let’s see how.
we know that
if p is even we can write N p = N p/2 * N p/2 = (N p/2) 2 and
if p is odd we can wrte N p = N * (N (p-1)/2 * N (p-1)/2) = N * (N (p-1)/2) 2
for example : 24 = 22 * 22
also, 25 = 2 * (22 * 22)
From this definaion we can derive this recurrance relation as
if p is even
result = ( func(N, p/2) ) 2
else
result = N * ( func(N, (p-1)/2) ) 2
Below is the implementation of the above approach in python3
Python3
# Python3 code to recursively find# the power of a number# Recursive function to find N^P.def power(N, P): # If power is 0 then return 1 if P == 0: return 1 # Recurrence relation if P%2 == 0: result = power(N, P//2) return result * result else : result = power(N, (P-1)//2) return N * result * result # Driver codeif __name__ == '__main__': N = 5 P = 2 print(power(N, P)) |
25
Time Complexity: O(log P), For log2P recursive calls.
Auxiliary Space: O(log P), For recursion call stack.
