Python program to find the power of a number using recursion

Last Updated : 02 May, 2023

Given a number N and power P, the task is to find the power of a number ( i.e. N^P ) using recursion.

Examples:

Input: N = 2 , P = 3
Output: 8

Input: 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 code
if __name__ == '__main__':
    N = 5
    P = 2
 
    print(power(N, P))

Output

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) ² and

if p is odd we can wrte N ^p= N * (N^(p-1)/2 * N ^(p-1)/2) = N * (N ^(p-1)/2) ²

for example : 2⁴ = 2²* 2²

also, 2⁵ = 2 * (2² * 2²)

From this definaion we can derive this recurrance relation as

if p is even

result = ( func(N, p/2) ) ²

else

result = N * ( func(N, (p-1)/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 code
if __name__ == '__main__':
    N = 5
    P = 2
 
    print(power(N, P))

Output

Time Complexity: O(log P), For log₂P recursive calls.
Auxiliary Space: O(log P), For recursion call stack.

A

ariesha1702

Improve

Previous Article

How to Print Multiple Arguments in Python?

Sorting objects of user defined class in Python

Similar Reads

Python program to find the factorial of a number using recursion

A factorial is positive integer n, and denoted by n!. Then the product of all positive integers less than or equal to n. [Tex]n! = n*(n-1)*(n-2)*(n-3)*....*1 [/Tex] For example: [Tex]5! = 5*4*3*2*1 = 120 [/Tex] In this article, we are going to calculate the factorial of a number using recursion. Examples: Input: 5 Output: 120 Input: 6 Output: 720 I

Python Program to Find the Total Sum of a Nested List Using Recursion

A nested list is given. The task is to print the sum of this list using recursion. A nested list is a list whose elements can also be a list. Examples : Input: [1,2,[3]] Output: 6 Input: [[4,5],[7,8,[20]],100] Output: 144 Input: [[1,2,3],[4,[5,6]],7] Output: 28 Recursion: In recursion, a function calls itself repeatedly. This technique is generally

Python program to find power of a number

Given a number N and power P. The task is to write a Python program to find the power of a number using recursion. Definition: Power of a number can be defined as multiplication of the number repetitively the number of times of its power. Example: Input: Number=2 Power =3 Output: 2 power 3 = 8 Python program to find power of a number using Iterativ

Python Program to Flatten a Nested List using Recursion

Given a nested list, the task is to write a python program to flatten a nested list using recursion. Examples: Input: [[8, 9], [10, 11, 'geeks'], [13]] Output: [8, 9, 10, 11, 'geeks', 13] Input: [['A', 'B', 'C'], ['D', 'E', 'F']] Output: ['A', 'B', 'C', 'D', 'E', 'F'] Step-by-step Approach: Firstly, we try to initialize a variable into the linked l

Python Program to Flatten a List without using Recursion

The task is to convert a nested list into a single list in Python i.e no matter how many levels of nesting are there in the Python list, all the nested have to be removed in order to convert it to a single containing all the values of all the lists inside the outermost brackets but without any brackets inside. In other words, an element in a list c

Python Program to Count Vowels in a String Using Recursion

Given a string, our task is to count the number of vowels in the string using recursion in Python and return the number of vowels. Examples: Input: acbedOutput: 2Input: geeksforgeeksOutput: 5Explanation: We are counting vowels in a string and printing the number of vowels.Python Program to Count Vowels in a String Using RecursionWe can use a recurs

Python Program to Display Fibonacci Sequence Using Recursion

We are given a task to write the Fibonacci sequence using recursion. we will take the range as input of integer and then print the Fibonacci Sequence. In this article, we will see the method of Python Program to Display Fibonacci Sequence Using Recursion. Example: Input: n = 9Output: 0 1 1 2 3 5 8 13 21Explanation: Here, we have n = 9, and we print

Find the value of ln(N!) using Recursion

Given a number N, the task is to find the log value of the factorial of N i.e. log(N!).Note: ln means log with base e.Examples: Input: N = 2 Output: 0.693147 Input: N = 3 Output: 1.791759 Approach:Method -1: Calculate n! first, then take its log value.Method -2: By using the property of log, i.e. take the sum of log values of n, n-1, n-2 ...1. ln(n

Python Program to find whether a no is power of two

Given a positive integer, write a function to find if it is a power of two or not.Examples : Input : n = 4 Output : Yes 22 = 4 Input : n = 7 Output : No Input : n = 32 Output : Yes 25 = 32 1. A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2. C/C++ Code # Python3 Program t

Python | All Permutations of a string in lexicographical order without using recursion

Write a python program to print all the permutations of a string in lexicographical order. Examples: Input : python Output : hnopty hnopyt hnotpy hnotyp hnoypt ...... ytpnho ytpnoh ytpohn ytponh Input : xyz Output : xyz xzy yxz yzx zxy zyx Method 1: Using the default library itertools function permutations. permutations function will create all the

Article Tags :

Practice Tags :

python