Power Using Recursion: flowchart, algorithm and program
This program reads x and n and prints x raised to the power n using a recursive function power(x, n). It uses the idea that x^n = x * x^(n-1), and x^0 = 1 stops the recursion.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read x.
- Step 3: Read n.
- Step 4: Call power(x, n).
- Step 5: If n == 0, go to step 6; otherwise go to step 7.
- Step 6: Return 1. Go to step 8.
- Step 7: return x * power(x, n - 1). Go to step 5.
- Step 8: Print x, n, result.
- Step 9: Stop.
Program in C, Python and Java
Power Using Recursion program in C
#include <stdio.h>
long long power(int x, int n) {
if (n == 0)
return 1;
return x * power(x, n - 1);
}
int main() {
int x, n;
printf("Enter x: ");
scanf("%d", &x);
printf("Enter n: ");
scanf("%d", &n);
printf("%d to the power %d = %lld\n", x, n, power(x, n));
return 0;
}Power Using Recursion program in Python
def power(x, n):
if n == 0:
return 1
return x * power(x, n - 1)
x = int(input("Enter x: "))
n = int(input("Enter n: "))
print(x, "to the power", n, "=", power(x, n))Power Using Recursion program in Java
import java.util.Scanner;
public class Main {
static long power(int x, int n) {
if (n == 0)
return 1;
return x * power(x, n - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter x: ");
int x = sc.nextInt();
System.out.print("Enter n: ");
int n = sc.nextInt();
System.out.println(x + " to the power " + n + " = " + power(x, n));
}
}
Sample input: x = 2, n = 5
Output: 2 to the power 5 = 32
How it works
- The base case is n == 0: power returns 1, because any number to the power 0 is 1.
- For any other n, power returns x * power(x, n - 1). Each call solves a slightly smaller problem with n reduced by 1.
- For x = 2, n = 5 the calls go power(2,5) -> power(2,4) -> power(2,3) -> power(2,2) -> power(2,1) -> power(2,0).
- When power(2,0) returns 1, the calls finish in reverse order: 2*1 = 2, 2*2 = 4, 2*4 = 8, 2*8 = 16, 2*16 = 32.
- The return type is long long so larger results fit, and main prints it with %lld.
Dry run (trace table)
| Step | Line | Box | x | n | Output |
|---|---|---|---|---|---|
| 1 | 9 | Start | |||
| 2 | 12 | Read x | 2 | Enter x: | |
| 3 | 14 | Read n | 2 | 5 | Enter n: |
| 4 | 15 | Call power(x, n) | 2 | 5 | |
| 5 | 4 | n == 0? | 2 | 5 | |
| 6 | 6 | return x * power(x, n - 1) | 2 | 5 | |
| 7 | 4 | n == 0? | 2 | 4 | |
| 8 | 6 | return x * power(x, n - 1) | 2 | 4 | |
| 9 | 4 | n == 0? | 2 | 3 | |
| 10 | 6 | return x * power(x, n - 1) | 2 | 3 | |
| 11 | 4 | n == 0? | 2 | 2 | |
| 12 | 6 | return x * power(x, n - 1) | 2 | 2 | |
| 13 | 4 | n == 0? | 2 | 1 | |
| 14 | 6 | return x * power(x, n - 1) | 2 | 1 | |
| 15 | 4 | n == 0? | 2 | 0 | |
| 16 | 5 | return 1 | 2 | 0 | |
| 17 | 6 | return x * power(x, n - 1) | 2 | 1 | |
| 18 | 6 | return x * power(x, n - 1) | 2 | 2 | |
| 19 | 6 | return x * power(x, n - 1) | 2 | 3 | |
| 20 | 6 | return x * power(x, n - 1) | 2 | 4 |
Time and space complexity
Time: O(n) · Space: O(n). The function calls itself n times, doing constant work per call, and the recursion stack grows to depth n.
Common mistakes
- Forgetting the base case n == 0, so the function keeps calling itself and crashes with a stack overflow.
- Calling power(x, n) instead of power(x, n - 1), so n never gets smaller and the recursion never ends.
- Entering a negative n: this code never reaches n == 0 and recurses forever. Negative powers need extra handling.
- Using int as the return type and getting overflow for results like 2^40; use long long and print with %lld.
Viva questions
Q1. What is the base case in your power function, and why is it needed?
The base case is n == 0, which returns 1 because any number raised to 0 is 1. Without it the function would keep calling itself with smaller and smaller n and never stop, causing a stack overflow.
Q2. Why does the base case return 1 and not 0?
The recursion multiplies results together, so the base value must be the multiplicative identity, which is 1. If it returned 0, every answer would become 0.
Q3. Trace power(2, 3). How do the calls and returns happen?
power(2,3) calls power(2,2), which calls power(2,1), which calls power(2,0) returning 1. Then the returns unwind: 2*1 = 2, 2*2 = 4, 2*4 = 8, so the answer is 8.
Q4. What happens if the user enters a negative n, such as n = -2?
n never reaches 0 because n-1 keeps getting more negative, so the recursion is infinite and the program crashes with a stack overflow. We should check for n < 0 and either reject it or compute 1/power(x, -n) using double.
Q5. What is the output for x = 0 and n = 0, and for x = 5 and n = 1?
power(0,0) returns 1 because the base case fires first, which matches the usual convention 0^0 = 1. power(5,1) returns 5 * power(5,0) = 5.
Q6. Why is the return type long long instead of int?
Powers grow very quickly and overflow an int, so long long gives a bigger range, up to about 9.2 * 10^18. Even so, something like 10^19 or 2^64 will still overflow.
Q7. What is the time and space complexity of this program?
Time is O(n) because there are n+1 calls, each doing one multiplication. Space is also O(n) because each pending call takes a stack frame.
Q8. What would change if you wanted a faster version?
Use exponentiation by squaring: compute half = power(x, n/2), then return half*half, with an extra factor x if n is odd. This reduces the number of calls to O(log n), both in time and stack depth.
Frequently asked questions
What is the base case in the recursive power program?
The base case is n == 0, where the function returns 1. Without it the recursion would never stop.
What is the time complexity of power(x, n) using this recursion?
It is O(n), because the function makes n + 1 calls, one for each value of n from n down to 0. It also uses O(n) stack space.
Does this program work for negative n?
No. With a negative n the value never reaches 0, so the recursion does not stop. To support it, compute power(x, -n) and return 1 divided by that result using floating-point numbers.