J'essaie d'apprendre à utiliser des fonctions récursives, mais je ne comprends pas ce qui se passe du tout.
function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
alert(power(4,4));
7 Réponses :
Vous avez besoin d'un cas de base en récursivité de sorte qu'il s'arrête en s'appuyant. Dans ce cas, la fonction de puissance s'appelle pour toujours (Eh bien, jusqu'à ce que l'interpréteur JavaScript abandonne) car l'exposant va à l'infini négatif.
Une fonction récursive s'appelle lui-même. Vous avez donc besoin d'un mécanisme pour le dire de vous arrêter ou vous serez dans une boucle infinie. Dans votre cas, vous revenez toujours et ne fournissez aucun moyen de quitter la boucle. D'où le rangeError.
Une fonction récursive s'appelle lui-même. C'est la définition de cela.
Cela apporte un problème: il s'appelle indéfiniment. Cela ira donc pour toujours, c'est pourquoi vous obtenez des débordements de pile. P>
à la place, vous devez vous arrêter à un moment donné. C'est là que la clause Lors de l'exécution de vu d'un peu d'angle différent: p>
Si vous remplacez tout dans chaque précédent, vous obtiendrez: P> si code> est entrée dans. Quand exponent == 0 code>, vous n'appelez pas la fonction, mais arrêtez le processus. P> Power (3, 3) Code>, il ira comme: p>
puissance (4, 4) code> est défini comme 4 * POWER (4, 3) code> par la fonction. LI>
puissance (4, 3) code> est défini comme 4 * POWER (4, 2) code> par la fonction. LI>
puissance (4, 2) code> est défini comme 4 * POWER (4, 1) code> par la fonction. LI>
puissance (4, 1) code> est défini comme 4 * POWER (4, 0) code> par la fonction. LI>
puissance (4, 0) code> est défini comme 1 code> par la fonction. LI>
ul> power(4, 4)
equals 4 * power(4, 3)
equals 4 * 4 * power(4, 2)
equals 4 * 4 * 4 * power(4, 1)
equals 4 * 4 * 4 * 4 * power(4, 0)
equals 4 * 4 * 4 * 4 * 1
equals 256
Ah je comprends maintenant. Y a-t-il des avantages à l'utilisation de la récursivité au lieu d'une boucle? Je suppose que les boucles seraient moins chères.
En fait, il y a encore une chose que je ne comprends pas encore. Je ne comprends pas pourquoi la première partie de la déclaration IF doit revenir 1. Pourquoi ne puis-je pas simplement utiliser une pause?
@Dan: Eh bien, la récursivité peut être une approche plus élégante. Il est probablement plus cher, mais votre exemple montre une utilisation compacte et agréable de la récursivité. En ce qui concerne break , ce mot clé signifie quelque chose de différent. C'est de sortir des boucles, pas de fonctions. Si vous regardez la ligne avant-dernière ligne de mon exemple, vous voyez que puissance (3, 0) doit renvoyer 1 (là, vous l'avez, retour ).
Merci d'avoir expliqué. Je comprends la partie où si Exponent == 1, il renvoie 1 et n'exécute pas le corps de la fonction. Pourquoi alors, ne renvoie-t-il pas 1 lorsque je alerte le pouvoir (4,4) et au lieu de la page 4 * 4 * 4 * 4? EDIT: En jouant avec la fonction, j'ai remarqué si je change la première partie de la déclaration IF à: Si (exponent == 0) renvoie 2, il le double. Je suppose que je ne comprends pas le retour, ni la fonction complètement. Je vais y arriver.
@Dan: il fait 4 * 4 * 4 * 4 * 1 . Si vous modifiez ce 1 sur 2 , vous pouvez voir qu'il fera * 2 , c'est-à-dire doubler le résultat.
@Dan: peut-être alerter les valeurs entre Aide: jsfiddle.net/pimvdb/yhcfr .
Merci, vous avez été une grande aide jusqu'à présent. Je joue avec ce morceau de code et je comprends la plupart de ce qui se passe. Le seul problème que je n'ai toujours pas, c'est pourquoi il se multiplie par 1. Je pensais que si vous, par exemple, le retour 1, vous définissez la fonction à l'égalité 1. En écrivant cela, je pense que je peux avoir juste compris ça. Lorsque Exponent == 1, vous multipliez toujours la base par la fonction de fonction et soustrayez 1 de l'exposant, ce qui le fait 0. Il doit encore aller si le corps de la puissance, de sorte qu'il passe à la première partie de la déclaration IF et multiplie par 1.Est-ce que ça va?
@Dan: Oui, je pense que tu l'as eu. Peut-être que mon édition aide aussi un peu. Il vous suffit de l'obtenir, alors c'est plutôt facile en fait :)
Votre édition rend tout plus clair pour moi. Espérons que cela a du sens pour les autres avec la même question. Merci!
@PIMVDB Merci d'avoir écrit en code ce que la récursion équivaut à; Il aide à clarifier la manière dont le calcul se passe dans les coulisses.
Vous devez lui donner des conditions de coin car sinon il continuera à nous appeler encore et encore. Parce que la taille de la pile est limitée, elle atteindra la fin de la mémoire de pile, puis une erreur sera lancée.
Le SI crée un chèque pour arrêter la récursion lorsque l'exposant atteint zéro. Sans cela, il continuera avec des valeurs négatives et ne s'arrête jamais.
Notez que la fonction s'appelle elle-même. Dans votre premier exemple, la fonction s'appelle elle-même, puis la nouvelle fonction appelle elle-même et ainsi de suite. En interne, votre ordinateur stocke ces appels de fonction dans une structure de mémoire appelée pile. Lorsqu'il n'y a plus de mémoire pour stocker les appels de fonction, vous avez dépassé la taille de la pile d'appels.
Dans le deuxième exemple, vous avez un moyen d'échapper à ce cercle vicieux. Le boîtier de base permet de revenir à la fonction, puis de "POP" la méthode appelle la pile.
Notez que dans votre deuxième exemple, vous pouvez commencer par alerte (puissance (4, -1)) et Vous rencontrerez à nouveau le même problème, car votre fonction soustrait-elle maintenant la soustraire de -1, vous donnant -2, etc. Vous pouvez fortifier le code en utilisant ... à la place.
Récursion appelle réellement la fonction dans son propre corps de fonction à nouveau et à nouveau jusqu'à ce que vous obtenez le résultat souhaité.
public int FactorialOfNumber(int k) {
if (k==1)
return 1;
else
return k * FactorialOfNumber(k-1); //Function called within Function.
}