ISC Practicals and Theory - Power Function (Recursive) (OOP)

This program finds $x^n$ using a recursive method, with the base and exponent stored as data members of an object. A constructor sets them, and the recursive method compute() calls itself with a smaller exponent each time.

Definition

$x^n$ is $x$ multiplied by itself $n$ times. $x^0 = 1$, and for $n \geq 1$, $x^n = x \times x^{n-1}$. For example $(-2)^3 = (-2) \times (-2) \times (-2) = -8$.

A recursive method needs a base case (stops without calling itself) and a recursive case (calls itself with a smaller problem).

The program accepts a base from -9 to 9 and an exponent from 0 to 15. A negative exponent is rejected, because $x^{-n} = 1/x^n$ is not a whole number, and these limits keep the answer inside a long (the largest is $9^{15} = 205891132094649$). $0^0$ is taken as 1, which is a convention: the base case returns 1 for every base.

Algorithm

1. Start. In main(), read the base b and the exponent e with a Scanner.
2. Create the object ob with new RecPower(b, e). The constructor copies them into the data members base and exp and sets answer to 0.
3. Call isValid(). It returns true only if base is from -9 to 9 and exp is from 0 to 15; otherwise print an error message and stop.
4. Call findPower(), which calls compute(exp) and stores the value in answer. Inside compute(k):
   • Base case: if k == 0, return 1.
   • Recursive case: otherwise return base * compute(k - 1). The base is a data member, so only the exponent k is passed on.
5. Call show() to print the answer.
6. Stop.

Program

The constructor RecPower() stores the values, isValid() checks the range, compute() is recursive, findPower() stores its value and show() prints it.

import java.util.*;
/** Class RecPower: stores a base and an exponent and finds base raised to exponent using recursion. */
class RecPower
{
    int base;     // the number to be multiplied
    int exp;      // the exponent (0 to 15)
    long answer;  // base raised to exp

    /** Constructor: stores the given base and exponent, and sets answer to 0. */
    RecPower(int b, int e)
    {
        base = b;
        exp = e;
        answer = 0;
    }

    /** Returns true if base is -9 to 9 and exp is 0 to 15. */
    boolean isValid()
    {
        return (base >= -9 && base <= 9 && exp >= 0 && exp <= 15);
    }

    /**
     * Recursive method: returns base raised to the power k.
     * k: the exponent for this call (k >= 0)
     */
    long compute(int k)
    {
        if (k == 0)                    // base case: base^0 = 1
            return 1;
        return base * compute(k - 1);  // recursive case: base^k = base * base^(k-1)
    }

    /** Calls compute() with the stored exponent and keeps the value in answer. */
    void findPower()
    {
        answer = compute(exp);
    }

    /** Shows the answer. */
    void show()
    {
        System.out.println(base + " raised to " + exp + " = " + answer);
    }

    /** main: reads the input, creates the object and calls the methods. */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the base (-9 to 9): ");
        int b = sc.nextInt();
        System.out.print("Enter the exponent (0 to 15): ");
        int e = sc.nextInt();
        RecPower ob = new RecPower(b, e);   // object created with the constructor
        if (ob.isValid())
        {
            ob.findPower();
            ob.show();
        }
        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): -2
Enter the exponent (0 to 15): 3
-2 raised to 3 = -8

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

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

Dry run

Take base 2 and exponent 4. The constructor sets base = 2 and exp = 4. findPower() calls compute(4).

Returning up: 1, then 2 x 1 = 2, 2 x 2 = 4, 2 x 4 = 8, 2 x 8 = 16. answer becomes 16 and show() 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."
2. Sum of digits "Using recursive technique, find the sum of the digits of a number."
3. Factorial "Using recursive technique, find the factorial of a number."