Doubt over Recursion in a power method

Question

Doubt over Recursion in a power method

Navigation

#1 by (3 votes)

2

I did not 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

asked by anonymous 05.06.2018 / 01:43

1 answer

Totalize column values of an HTML table, with decimal result Help on select to bring field even though null

score 3 · Accepted Answer

First I'll give a tidy 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;
    }
}

Notice that I changed the if condition. This is important because your original code did not know how to handle the exponent's case being zero.

Let's look at some math:

Take, for example, 3 5 :

3 5 = 3 × 3 × 3 × 3 × 3 = (3 × 3 × 3 × 3) × 3 = 3 4 × 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% from% to% with%. Here is the recursion.

Moving on:

3 4 = 3 × 3 × 3 × 3 = (3 × 3 × 3) × 3 = 3 3 × 3

3 3 = 3 × 3 × 3 = (3 × 3) × 3 = 3 2 × 3

3 2 = 3 × 3 = (3) × 3 = 3 1 × 3

3 1 = 3

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

3 5 = 3 4 × 3 = potencia(3, 5) × 3

3 4 = 3 3 × 3 = potencia(3, 4) * 3 × 3

3 3 = 3 2 × 3 = potencia(3, 4) × 3

3 2 = 3 1 × 3 = potencia(3, 3) × 3

3 1 = 3

That is, in your call stack 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 potencia(3, 2) (the base). And then he starts to use the computed result and peg these calls from potencia(3, 1) to 3 :

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

Result of potencia(3, 5) : 3 2 = 3 1 × 3 = potencia(3, 1) × 3 = 3 × 3 = 9

Result of potencia(3, 2) : 3 3 = 3 2 × 3 = potencia(3, 1) × 3 = 9 × 3 = 27

Result of potencia(3, 3) : 3 4 = 3 3 × 3 = potencia(3, 2) × 3 = 27 × 3 = 81

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

That is, what the potencia(3, 5) method is doing is to reduce potentiation by potencia(3, 4) by a multiplication by potencia power. Since this is recursive, the potentiation by e will in turn be reduced to a potentiation by e - 1 , which will be reduced by a potentiation by e - 1 , until the potency is 1.

And why did I change the e - 2 to stop at power 0 instead of 1? Because in the case of the exponent being 0, the result of the power is always 1 and the case of the exponent is 1 also reduces to a multiplication by the exponent 0 as in the other exponents, producing this:

Result of e - 3 : 1

Result of if : 3 1 = 3 0 × 3 = potencia(3, 0) × 3 = 1 × 3 = 3