java - recursividad - Método recursivo para x ^ n optimizado para cuando n es par

recursividad con string en java

Question

Necesito escribir un método recursivo utilizando Java llamado power que toma un doble xy un entero ny que devuelve x ^ n. Esto es lo que tengo hasta ahora.

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    else
        return x * (power(x, n-1));

}

Este código funciona como se esperaba. Sin embargo, estoy tratando de hacer un esfuerzo adicional y realizar el siguiente ejercicio opcional:

"Desafío opcional: puedes hacer que este método sea más eficiente, cuando n es par, usando x ^ n = (x ^ (n / 2)) ^ 2."

No estoy seguro de cómo implementar esa última fórmula cuando n es par. No creo que pueda usar la recursividad para eso. He intentado implementar lo siguiente, pero tampoco funciona porque no puedo tomar el doble de la potencia de un int.

if (n%2 == 0)
        return (x^(n/2))^2;

¿Puede alguien señalarme en la dirección correcta? Siento que me falta algo obvio. Toda ayuda apreciada.

Answer 1

Al hacer un pequeño cambio en su función, reducirá el número de llamadas recursivas realizadas:

public static double power(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }

    if (n % 2 == 0) {
        double temp = power(x, n / 2);
        return temp * temp;
    } else {
        return x * (power(x, n - 1));
    }
}

Answer 2

Cuando n es par, la fórmula es exactamente lo que usted escribió: divida n por dos, llame al power recursivamente y cuadre el resultado.

Cuando n es impar, la fórmula es un poco más compleja: resta 1 de n , realiza una llamada recursiva para n/2 , cuadra el resultado y multiplica por x .

if (n%2 == 0)
    return (x^(n/2))^2;
else
    return x*(x^(n/2))^2;

n/2 trunca el resultado, por lo que la resta de 1 no se hace explícitamente. Aquí hay una implementación en Java:

public static double power(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    double pHalf = power(x, n/2);
    if (n%2 == 0) {
        return pHalf*pHalf;
    } else {
        return x*pHalf*pHalf;
    }
}

Demo.

Answer 3

Es exactamente el mismo principio que para x ^ n == x * (x ^ (n-1)): inserta tu función recursiva para x ^ (n / 2) y (...) ^ 2, pero asegúrate de ponerte Ingrese una recursión infinita para n == 2 (como 2 es par, también):

if (n % 2 == 0 && n > 2) 
  return power(power(x, n / 2), 2);
} 

Alternativamente, puedes usar una variable intermedia:

if (n % 2 == 0) {
  double s = power(x, n / 2);
  return s * s;
}

Probablemente también manejaría 2 como un caso especial, y evitaría la condición "y" y la variable adicional:

public static double power(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n == 2) return x * x;
  if (n % 2 == 0) return power(power(x, n / 2), 2);
  return x * (power(x, n - 1));
}

PD, creo que esto debería funcionar, también :)

public static double power(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n == 2) return x * x;
  return power(x, n % 2) * power(power(x, n / 2), 2);
}

Answer 4

Esto solo me recuerda que se podría hacer más optimización y este código siguiente.

class Solution:
# @param x, a float
# @param n, a integer
# @return a float
def pow(self, x, n):
    if n<0:
        return 1.0/self.pow(x,-n)
    elif n==0:
        return 1.0
    elif n==1:
        return x
    else:
        m = n & (-n)
        if( m==n ):
            r1 = self.pow(x,n>>1)
            return r1*r1
        else:
            return self.pow(x,m)*self.pow(x,n-m)

lo que es más, el resultado intermedio podría ser memorizado y evitar cálculos redundantes.

Answer 5

Sugerencia: La ^ operación no realizará exponentiation en Java, pero la función que escribió, el power hará.

Además, no olvides cuadrar un número es lo mismo que simplemente multiplicarlo por sí mismo. No se necesita una llamada de función.

Answer 6

Ya que

x^(2n) = (x^n)^2

Puedes agregar esta regla a tu método, ya sea usando la función de potencia que escribiste, como sugirió Stefan Haustein, o usando el operador de multiplicación regular, ya que parece que puedes hacerlo.

Tenga en cuenta que no hay necesidad de ambos casos base n = 1 yn = 0, uno de ellos es suficiente (preferiblemente use el caso base n = 0, ya que de lo contrario su método no estaría definido para n = 0).

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        double val = power(x, n/2);
        return val * val;
    else
        return x * (power(x, n-1));
}

No es necesario verificar que n> 2 en ninguno de los casos.