Méthode récursive pour x^n optimisée lorsque n est pair

Question

Je dois écrire une méthode récursive en utilisant Java appelée puissance qui prend un double x et un entier n et qui retourne x^n. Voici ce que j'ai jusqu'à présent.

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));

}

Ce code fonctionne comme prévu. Cependant, j'essaie d'aller plus loin et d'effectuer l'exercice facultatif suivant :

"Défi facultatif : vous pouvez rendre cette méthode plus efficace, lorsque n est pair, en utilisant x^n = (x^(n/2))^2."

Je ne sais pas comment mettre en œuvre cette dernière formule lorsque n est pair. Je ne pense pas pouvoir utiliser la récursion pour cela. J'ai essayé d'appliquer la formule suivante, mais elle ne fonctionne pas non plus car je ne peux pas prendre un double à la puissance d'un int.

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

Quelqu'un peut-il m'indiquer la bonne direction ? J'ai l'impression de passer à côté de quelque chose d'évident. Toute aide est la bienvenue.

Answer 1

C'est exactement le même principe que pour x^n == x*(x^(n-1)) : Insérez votre fonction récursive pour x^(n/2) et (...)^2, mais assurez-vous de ne pas entrer dans une récursion infinie pour n == 2 (car 2 est pair, aussi) :

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

Sinon, vous pouvez simplement utiliser une variable intermédiaire :

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

Je traiterais probablement aussi le 2 comme un cas particulier, en évitant la condition "et" et la variable supplémentaire :

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));
}

P.S. Je pense que cela devrait aussi fonctionner :)

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 2

En n est pair, la formule est exactement ce que vous avez écrit : diviser n par deux, appelez power récursivement, et élever au carré le résultat.

En n est impair, la formule est un peu plus complexe : soustraire 1 de n , faire un appel récursif pour n/2 , élever le résultat au carré, et multiplier par x .

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

n/2 tronque le résultat, donc la soustraction de 1 n'est pas fait explicitement. Voici une implémentation 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;
    }
}

Démonstration.

Answer 3

Indice : le ^ n'effectuera pas l'exponentiation en Java, mais la fonction que vous avez écrite, power volonté.

N'oubliez pas non plus que l'élévation au carré d'un nombre revient à le multiplier par lui-même. Aucun appel de fonction n'est nécessaire.

Answer 4

En apportant une petite modification à votre fonction, cela réduira le nombre d'appels récursifs effectués :

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 5

Depuis

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

vous pouvez ajouter cette règle à votre méthode, soit en utilisant la fonction puissance que vous avez écrite, comme Stefan Haustein l'a suggéré, soit en utilisant l'opérateur de multiplication ordinaire, puisqu'il semble que vous soyez autorisé à le faire.

Notez qu'il n'est pas nécessaire d'avoir les deux cas de base n=1 et n=0, l'un des deux suffit (utilisez de préférence le cas de base n=0, car sinon votre méthode ne serait pas définie pour 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));
}

Il n'est pas nécessaire de vérifier que n>2 dans aucun des cas.