Comment fonctionne la récursivité en Java?

Parce qu'en fait rien ne se passe avant que le dernier appel à factorial () ne renvoie 1 . En interne, tous les résultats intermédiaires sont «empilés» sur la pile puis «empilés» lorsque la fonction revient.

Donc en fait, un appel à factorial (3) fait

factorial(0) = 1
factorial(1) = 1 * (1)
factorial(2) = 2 * (1 * (1))
factorial(3) = 3 * (2 * (1 * (1)))
factorial(4) = 4 * (3 * (2 * (1 * (1))))
...

Une fois que la factorielle (0) est finalement revenue, toutes les multiplications sont cumulées:

1 * 1 * 2 * 3 = 6

Ou écrites dans l'autre sens:

factorial(3) = 3 * factorial(2) -->> 3 on the heap
factorial(2) = 2 * factorial(1) -->> 2,3 on the heap
factorial(1) = 1 * factorial(0) -->> 1,2,3 on the heap
factorial(0) = 1

Chaque parenthèse ouvrante est un appel de fonction qui pousse une valeur sur la pile, et les multiplications ne peuvent se produire que lorsque les valeurs gauche et droite sont connues, ce qui c'est quand il atteint 0 et renvoie 1.

La récursivité n'est en aucun cas un concept facile - la plupart des gens ont des problèmes avec elle, vous n'êtes donc pas seul.

Penser récursivement à un problème signifie que certains calculs sont répétés jusqu'à ce que le problème soit résolu (ie le cas de base est atteint ou la méthode est épuisée. Pour le Factoriel, c'est quand n = 0, pour le nombre print, la méthode est épuisé [ne fait rien]). Lorsque cela se produit, le calcul le plus récent est renvoyé au niveau de récursivité jusqu'à ce qu'il ne reste plus de niveaux. Ainsi, le problème est résolu.

Voici une analogie: pensez à ce processus comme si vous faisiez du minage. Le calcul (ou la procédure) pour le minage (en gros) consiste à creuser jusqu'à ce que vous trouviez ce que vous voulez (disons des gemmes). Vous commencez à la surface de la Terre. Y a-t-il des gemmes? Cette question est votre cas de base: vous arrêterez de miner lorsque vous trouverez vos gemmes. S'il n'y a pas de gemmes, vous devez creuser plus profondément (descendre d'un niveau), vous appelez donc la procédure d'extraction. Vous vous demandez à nouveau, y a-t-il des gemmes? S'il n'y a pas de gemmes, vous devez creuser plus profondément, etc. Cela se répétera, ou se répétera, jusqu'à ce que vous puissiez répondre à la question par «Oui! J'ai trouvé des pierres précieuses. Une fois le scénario de base atteint, vous êtes au niveau le plus bas du processus, n'est-ce pas? Lors de l'exploitation minière, une fois que vous avez trouvé les gemmes, vous ne pouvez pas rester au fond de la mine. Vous devez retourner au sommet avec les gemmes que vous avez.

C'est la récursion en un mot. Maintenant, pour répondre à votre compréhension:

Vous avez raison avec le conditionnel, 10> = 1, alors appelez printNumbers (10 - 1), et ainsi de suite. Cependant, il imprime avec 1 car c'était la première chose retournée. Si vous regardez le code, vous remarquerez que printNumbers (10 - 1) est appelé avant System.out.println (n + "") ;. Cela signifie qu'avant l'impression de 10, printNumbers exécute 9. Lorsque nous arrivons à printNumbers (1), voici ce qui se passe:

• Un est-il supérieur ou égal à un? Oui, passons à autre chose.
• printNumbers (1 - 1)
• Est-ce que zéro est supérieur ou égal à un? Non, et comme il n'y a rien après le conditionnel, la méthode est épuisée et retourne.
• System.out.println (1 + "");
• Maintenant, printNumbers (1) est terminé, quelle est la prochaine étape?
• System.out.println (2 + "");
• Maintenant, printNumbers (2) est terminé, quelle est la prochaine étape?
• Et ainsi de suite, jusqu'à printNumbers (10) - le premier appel de printNumbers
• System.out.println (10 + "");
• Il n'y a rien d'autre, problème résolu!

C'est vraiment tout ce qu'il y a à faire. En cas de confusion, faites-le moi savoir!

Je suppose que cette question concerne plus l'ordre des calculs et pas tant la compréhension de l'idée de récursivité.

Avec la récursivité, les choses se passent à l'inverse de ce que vous avez répertorié. Cela fonctionne comme une pile au lieu d'une file d'attente. Si vous avez joué à des jeux de cartes comme MTG, cela fonctionne comme dans les jeux. La dernière chose "activée" est faite en premier.

En gros, la première fois que vous appelez la fonction factorielle, elle se bloque à ce stade:

//int n = 10;
private static void printNumbers(int n) {
    if(n >= 1) {
        printNumbers(n - 1);
        System.out.print(n + " ");
    }
}

Parce que votre Le programme attend maintenant le résultat de factoriel (n - 1) pour continuer.

Il continuera d'appeler des sous-programmes (qui, s'ils sont assez grands, peut provoquer une exception de dépassement de pile, le nom de ce site après).

Finalement, n sera égal à 0, et cette branche exécutera:

return n * factorial(n - 1); //been waiting forever...

Donc, en haut de votre stack, vous aurez factorial(1) en attente du résultat de factoriel (0) .

return 3 * 2; //2 replaces factorial(2), now ready to return.

Maintenant que 0 est pris en charge, 1 est prêt à renvoyer sa valeur.

return 2 * 1; //ready to return!

Nous sommes maintenant à N = 2, toujours coincé au même endroit.

return 2 * factorial(1); //need factorial(1) to continue!

Après le retour factoriel (1), nous obtenons:

return 1 * 1; //1 replaces factorial(0), now we can return!

Puis à N = 3 (ou factorial(3))

return 1 * factorial(0); //come on hurry up factorial(0)!

... et ainsi de suite jusqu'à

return 1;