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

  1. Step 1: Start.
  2. Step 2: Read x.
  3. Step 3: Read n.
  4. Step 4: Call power(x, n).
  5. Step 5: If n == 0, go to step 6; otherwise go to step 7.
  6. Step 6: Return 1. Go to step 8.
  7. Step 7: return x * power(x, n - 1). Go to step 5.
  8. Step 8: Print x, n, result.
  9. 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)

StepLineBoxxnOutput
19Start
212Read x2Enter x:
314Read n25Enter n:
415Call power(x, n)25
54n == 0?25
66return x * power(x, n - 1)25
74n == 0?24
86return x * power(x, n - 1)24
94n == 0?23
106return x * power(x, n - 1)23
114n == 0?22
126return x * power(x, n - 1)22
134n == 0?21
146return x * power(x, n - 1)21
154n == 0?20
165return 120
176return x * power(x, n - 1)21
186return x * power(x, n - 1)22
196return x * power(x, n - 1)23
206return x * power(x, n - 1)24

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.

More programs

← All programs

Try AI Flowchart free →