Doubt about Recursiveness in a Power Method

Asked

Viewed 1,226 times

2

I didn’t understand how recursion works in the method that performs potentiation. 

public class calculaPotencia {

    static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
        System.out.print("digite um número inteiro para base: ");
            int base = scan.nextInt();
        System.out.print("digite um número inteiro para o expoente: ");
            int exp = scan.nextInt();
        System.out.print("A potencia de " +base+ " elevado a " +exp+ " é: " + potencia(base,exp));
        System.exit(0);
    }
    static int potencia(int b,int e){
        if (e==1)
            return b;
        else
            return (potencia(b,e-1)*b);

    }

}
java recursion

1 answer

3


First I’m gonna fix the code:

public class CalculaPotencia {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.print("Digite um número inteiro para base: ");
        int base = scan.nextInt();
        System.out.print("Digite um número inteiro para o expoente: ");
        int exp = scan.nextInt();
        System.out.print("A potência de " + base
                + " elevado a " + exp + " é: " + potencia(base, exp));
    }

    public static int potencia(int b, int e) {
        if (e == 0) return 1;
        return potencia(b, e - 1) * b;
    }
}

Note that I changed the condition of if. This is important because your original code didn’t know how to handle the case of the exponent being zero.

Let’s see some math:

Let’s take for example, 35:

35 = 3 3 3 3 3 = (3 3 3 3) 3 = 34 3

Note that in this example, we reduce exponentiation by power 5 to an exponentiation by power 4 and a multiplication. That is, we reduce potencia(3, 5) for potencia(3, 4) * 3. Here occurs the recursion.

Going on:

34 = 3 3 3 = (3 3 3) 3 = 33 3

33 = 3 3 = (3 3) 3 = 32 3

32 = 3 3 = (3) 3 = 31 3

31 = 3

In the code, that up there is equivalent to this down here:

35 = 34 3 = potencia(3, 4) 3

34 = 33 3 = potencia(3, 3) 3

33 = 32 3 = potencia(3, 2) 3

32 = 31 3 = potencia(3, 1) 3

31 = 3

I mean, in your stack of calls you have:

potencia(3, 5)
potencia(3, 4)
potencia(3, 3)
potencia(3, 2)
potencia(3, 1)

And this is where your original algorithm stops and returns 3 (the base). And then he starts using the computed result and goes to unpacking those calls from potencia(3, 1) up to the potencia(3, 5):

Result of potencia(3, 1): 31 = 3

Result of potencia(3, 2): 32 = 31 3 = potencia(3, 1) 3 = 3 3 = 9

Result of potencia(3, 3): 33 = 32 3 = potencia(3, 2) 3 = 9 3 = 27

Result of potencia(3, 4): 34 = 33 3 = potencia(3, 3) 3 = 27 3 = 81

Result of potencia(3, 5): 35 = 34 3 = potencia(3, 4) 3 = 81 3 = 243

That is, what the method potencia is to reduce potentiation by e by a multiplication by power e - 1. How this is recursive, potentiation by e - 1 will in turn be reduced to a potentiation by e - 2, which will be reduced by a potentiation by e - 3, until the power is 1.

And because I changed the if to stop at power 0 instead of 1? Because in the case of the exponent being 0, the power output is always 1 and the case of the exponent being 1 is also reduced to a multiplication by the exponent 0 as in the other exponents, producing this:

Result of potencia(3, 0): 1

Result of potencia(3, 1): 31 = 30 3 = potencia(3, 0) 3 = 1 3 = 3

Browser other questions tagged java recursion

You are not signed in. Login or sign up in order to post.