ISC Practicals and Theory - Power Function (Recursive)

The power function finds $x^n$, the number $x$ multiplied by itself $n$ times. Written with recursion, the method power() solves a bigger power by calling itself for a smaller exponent, until the exponent reaches 0.

Definition

$x^n$ means $x$ multiplied by itself $n$ times, where $x$ is the base and $n$ is the exponent. By definition $x^0 = 1$, and for $n \geq 1$:

$x^n = x \times x^{n-1}$

This second line is already recursive: a power is written using a smaller power of the same kind.

• $2^4 = 2 \times 2^3 = 2 \times 2 \times 2^2 = \ldots = 16$
• $(-3)^5 = -243$. An odd exponent keeps the negative sign; an even exponent would give a positive answer.

Recursion is a method calling itself. Every recursive method needs a base case (where it stops and returns directly) and a recursive case (where it calls itself with a smaller problem).

Limits used in this program

• Only exponents from 0 to 15 are accepted. A negative exponent is rejected, because $x^{-n} = 1/x^n$ is not a whole number.
• The base is limited to -9 to 9 so that the answer always fits in a long. The largest answer is $9^{15} = 205891132094649$. An int would overflow at $9^{10}$ already, so the result is stored in a long.
• $0^0$ is taken as 1 in this program. This is a convention, and it follows from the base case returning 1 for every base.

Algorithm

1. Start. In main(), create an object ob of the class Power.
2. Call accept() to read the base x and the exponent n.
3. Call isValid(). If x is not from -9 to 9, or n is not from 0 to 15, print an error message and stop.
4. Otherwise call power(x, n) and store the value in result. Inside power(b, e):
   • Base case: if e == 0, return 1.
   • Recursive case: otherwise return b * power(b, e - 1). Each call reduces the exponent by 1, so the calls must reach e == 0.
5. Call display() to print the result.
6. Stop.

Program

The method accept() reads the input, isValid() checks the range, power() is the recursive method and display() prints the answer.

import java.util.*;
/** Class Power: finds x raised to the power n using recursion. */
class Power
{
    int x;      // base
    int n;      // exponent (a whole number from 0 to 15)
    long result; // value of x raised to n

    /** Reads the base and the exponent from the user. */
    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the base (-9 to 9): ");
        x = sc.nextInt();
        System.out.print("Enter the exponent (0 to 15): ");
        n = sc.nextInt();
    }

    /** Checks the range. Returns true if x is -9..9 and n is 0..15. */
    boolean isValid()
    {
        return (x >= -9 && x <= 9 && n >= 0 && n <= 15);
    }

    /**
     * Recursive method: returns b raised to the power e.
     * b: base, e: exponent (e >= 0)
     */
    long power(int b, int e)
    {
        if (e == 0)                  // base case: any number to the power 0 is 1
            return 1;
        return b * power(b, e - 1);  // recursive case: b^e = b * b^(e-1)
    }

    /** Shows the result. */
    void display()
    {
        System.out.println(x + " raised to " + n + " = " + result);
    }

    /** main: creates the object and calls the methods. */
    public static void main(String args[])
    {
        Power ob = new Power();   // object of the class
        ob.accept();
        if (ob.isValid())
        {
            ob.result = ob.power(ob.x, ob.n);
            ob.display();
        }
        else
            System.out.println("Invalid input: base must be -9 to 9 and exponent 0 to 15");
    }
}

Variable description table

Sample input and output

Enter the base (-9 to 9): 2
Enter the exponent (0 to 15): 4
2 raised to 4 = 16

Enter the base (-9 to 9): -3
Enter the exponent (0 to 15): 5
-3 raised to 5 = -243

Enter the base (-9 to 9): 5
Enter the exponent (0 to 15): 0
5 raised to 0 = 1

Enter the base (-9 to 9): 2
Enter the exponent (0 to 15): -1
Invalid input: base must be -9 to 9 and exponent 0 to 15

Dry run

Take $x = 2$ and $n = 4$. isValid() returns true, so power(2, 4) is called. The calls go down until e is 0, then the values return up.

Returning up: power(2, 0) gives 1, then power(2, 1) = 2 x 1 = 2, power(2, 2) = 2 x 2 = 4, power(2, 3) = 2 x 4 = 8 and power(2, 4) = 2 x 8 = 16. So result = 16 and the program prints 2 raised to 4 = 16, the same as the first sample run.

Variations

1. Power using a loop "Write a program to find x raised to the power n without recursion, using a loop."
2. Negative exponent "Accept a negative exponent also and find the answer as a decimal number."
3. Sum of digits "Using recursive technique, find the sum of the digits of a number."
4. Factorial "Using recursive technique, find the factorial of a number."