Fonction de puissance récursive: approche

Je programme depuis un certain temps (débutant), et les fonctions récursives sont un concept quelque peu abstrait. Je ne dirais pas que je suis bloqué, le programme fonctionne bien, je me demande si la fonction elle-même pourrait être écrite sans la fonction pow dans le code (tout en faisant exactement ce que le problème suggère)

Problème: http://prntscr.com/30hxg9

Ma solution:

#include #include int power(int, int); int main(void) { int x, n; printf("Enter a number and power you wish to raise it to: "); scanf_s("%d %d", &x, &n); printf("Result: %d\n", power(n, x)); return 0; } int power(int x, int n) { if (n == 0) return 1; if (n % 2 == 0) return pow(power(x, n / 2), 2); else return x * power(x, n - 1); } 

J’ai essayé de faire ceci: power (power (x, n – 1), 2); mais l’exécution a échoué et je reviens toujours sur mes pas.

Lors de la réécriture de votre fonction, ne perdez pas de vue le principal avantage de la récursivité dans ce cas, qui consiste à réduire le nombre d’opérations de multiplication requirejses. Par exemple, si n = 8, il est beaucoup plus efficace de calculer x * x comme val1, alors val1 * val1 comme val2 et la réponse finale sous la forme val2 * val2 (3 multiplications) que de calculer x * x * x * x * x * x * x * x (7 multiplications).

Cette différence est sortingviale pour les petits entiers, mais elle importe si vous placez cette opération dans une grande boucle ou si vous remplacez les entiers par des représentations de très grands nombres ou peut-être des masortingces ginormeuses.

Voici un moyen de vous débarrasser de la fonction pow () sans vous priver de l’efficacité de la récursivité:

 #include #include int power(int, int); int main(void) { int x, n; printf("Enter a number and power you wish to raise it to: "); scanf_s("%d %d", &x, &n); printf("Result: %d\n", power(x, n)); return 0; } int power(int x, int n) { int m; if (n == 0) return 1; if (n % 2 == 0) { m = power(x, n / 2); return m * m; } else return x * power(x, n - 1); } 

Pour la fonction de puissance (disons, x à la nième puissance), vous avez deux cas:

 exponent=0 exponent=n 

Pour le premier cas, vous devez seulement renvoyer 1. Dans l’autre cas, vous devez redonner x à la puissance de n moins un. Là, vous avez seulement utilisé la fonction de manière récursive.

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

Le code:

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

ne fonctionne pas car lorsque n est pair, le pouvoir est appelé avec n = 2, qui est pair et puis, le pouvoir est appelé, avec n = 2, qui est pair et ensuite, le pouvoir est appelé avec n = 2 … jusqu’à … débordement de stack!

Solution simple:

 int power(int x, int n) { if (n == 0) return 1; if (n % 2 == 0) { if (n == 2) return x * x; return power(power(x, n / 2), 2); } else return x * power(x, n - 1); } 
 double result = 1; int count = 1; public double power(double baseval, double exponent) { if (count <= Math.Abs(exponent)){ count++; result *= exponent<0 ?1/baseval:baseval; power(baseval, exponent); } return result; } 

Cela fonctionne avec une valeur positive, négative et 0

Simple mais ne n nombre de multiplications. Les exemples ci-dessus sont plus efficaces car ils regroupent deux opérations en une itération

 int power(int x, int n) { if (n == 0) return 1; return x * power(x, n-1); } 

Voici une solution en ruby qui fonctionne aussi pour les exposants négatifs

 # for calculating power we just need to do base * base^(exponent-1) for ex: # 3^4 = 3 * 3^3 # 3^3 = 3 * 3^2 # 3^2 = 3 * 3^1 # 3^1 = 3 * 3^0 # 3^0 = 1 # --------------------------------------------------------------------------- # OPTIMIZATION WHEN EXPONENT IS EVEN # 3^4 = 3^2 * 3^2 # 3^2 = 3^1 * 3^1 # 3^1 = 3^0 # 3^0 = 1 # --------------------------------------------------------------------------- def power(base, exponent) if(exponent.zero?) return 1 end if(exponent % 2 == 0) result = power(base, exponent/2) result = result * result else result = base * power(base, exponent.abs-1) end # for handling negative exponent if exponent < 0 1.0/result else result end end # test cases puts power(3, 4) puts power(2, 3) puts power(0, 0) puts power(-2, 3) puts power(2, -3) puts power(2, -1) puts power(2, 0) puts power(0, 2) 

Mon approche avec C ++ ne fonctionne qu’avec des nombres non négatifs.

 #include  using namespace std; long long power(long long x, long long y) { if (y == 0) { return 1; } else { y--; return x*power(x,y); } } main() { long long n, x; cin >> n >> x; cout << power(n,x); } 
 int pow(int a, int n) { if(n == 0) return 1; if(n == 1) return a; int x = pow(a, n/2); if(n%2 == 0) { return x*x; } else { return a*x*x; } }