Apprendre Java (et la programmation) sur Udemy. Besoin d'aide pour comprendre la logique
Je regarde actuellement une vidéo sur la récursivité, et j'ai besoin d'aide avec la logique dedans.
Je ne comprends pas le "moment" de retour de l'algorithme. Voici le code:
public class App {
public static void main(String[] args) {
// E.g. 4! = 4*3*2*1 (factorial 4)
System.out.println(factorial(5));
}
private static int factorial(int value) {
//System.out.println(value);
if(value == 1) {
return 1;
}
return factorial(value - 1) * value;
}
}
Ce que je ne comprends pas, c'est la partie return 1;.
Lorsque la méthode calcule la factorielle de 4, elle se rappelle elle-même jusqu'à ce que la valeur devienne 1.
Mais quand value == 1, la méthode est supposée renvoyer 1 à l'appelant de la méthode.
Ce return 1 ne remplace-t-il pas return factorial(value - 1) * value;??
, Clairement, je ne comprends pas complètement comment return œuvres.
Merci d'avance :)
3 answers
Le point de chaque récursivité est "point d'arrêt", la condition, lorsque la récursivité ne continue pas, mais renvoie une valeur. Si ce point n'existe pas, la récursivité nevers se termine.
Voici comment il sera appelé:
System.out.println(factorial(5))
-return factorial(4)*5
--return factorial(3)*4
---return factorial(2)*3
----return factorial(1)*2
-----return 1
----return 1*2
---return 2*3
--return 6*4
-return 24*5
System.out.println(120)
Je pense que c'est plus clair, quand vous mettez "return" en dehors du comptage récursif, parce que vous faites plus de choses dans une ligne.
J'ai fait ce programme, ignorer la méthode "doMinuses", cela ne fait que des inconvénients pour rendre la sortie plus lisible. Il n' la même chose que votre programme. Vous n'avez pas à le lire, il suffit de regarder la sortie en premier.
public class App {
public static int origValue = 5;
public static void main(String[] args) {
System.out.println(factorial(origValue));
}
private static int factorial(int value) {
doMinuses(origValue-value);
System.out.println("Entered factorial("+value+")");
if(value == 1) {
doMinuses(origValue-value);
System.out.println("Returning 1");
return 1;
}
doMinuses(origValue-value);
System.out.println("Start countin factorial("+(value-1)+")*"+value);
int factorialResult = factorial(value - 1) * value;
doMinuses(origValue-value);
System.out.println("Returning result for factorial("+(value-1)+")*"+value + " = " + factorialResult);
return factorialResult;
}
private static void doMinuses(int count){
for (int i = 0; i < count; i++) {
System.out.print('-');
}
}
}
La sortie est
Entered factorial(5)
Start countin factorial(4)*5
-Entered factorial(4)
-Start countin factorial(3)*4
--Entered factorial(3)
--Start countin factorial(2)*3
---Entered factorial(2)
---Start countin factorial(1)*2
----Entered factorial(1)
----Returning 1
---Returning result for factorial(1)*2 = 2
--Returning result for factorial(2)*3 = 6
-Returning result for factorial(3)*4 = 24
Returning result for factorial(4)*5 = 120
120
La seule différence en dehors de l'impression du code est de changer cette ligne
return factorial(value - 1) * value;
À deux lignes, parce que c'est, ce qui se passe vraiment (surtout l'ordre de ce qui se passe).
int factorialResult = factorial(value - 1) * value;
return factorialResult;
J'ai édité la fonction encore plus pour la MEILLEURE sortie de tous les temps:)
public class App {
public static int origValue = 5;
public static void main(String[] args) {
System.out.println(factorial(origValue));
}
private static int factorial(int value) {
doMinuses(origValue - value);
System.out.println("Entered factorial(" + value + ")");
if (value == 1) {
doMinuses(origValue - value);
System.out.println("Returning 1");
return 1;
}
doMinuses(origValue - value);
System.out.println("Start countin factorial(" + (value - 1) + ")*" + value);
int factorialResult = factorial(value - 1);
doMinuses(origValue - value);
System.out.println("Finished counting factorial(" + (value - 1) + ") = " + factorialResult);
doMinuses(origValue - value);
System.out.println("Returning result for factorial(" + (value - 1) + ")*" + value + " = " + factorialResult + "*" + value + " = " + (factorialResult * value));
return factorialResult * value;
}
private static void doMinuses(int count) {
for (int i = 0; i < count; i++) {
System.out.print('-');
}
}
}
A cette sortie :
Entered factorial(5)
Start countin factorial(4)*5
-Entered factorial(4)
-Start countin factorial(3)*4
--Entered factorial(3)
--Start countin factorial(2)*3
---Entered factorial(2)
---Start countin factorial(1)*2
----Entered factorial(1)
----Returning 1
---Finished counting factorial(1) = 1
---Returning result for factorial(1)*2 = 1*2 = 2
--Finished counting factorial(2) = 2
--Returning result for factorial(2)*3 = 2*3 = 6
-Finished counting factorial(3) = 6
-Returning result for factorial(3)*4 = 6*4 = 24
Finished counting factorial(4) = 24
Returning result for factorial(4)*5 = 24*5 = 120
120
Return 1 remplace-t-il le return factorial(value - 1) * value;
Mais ce que fait cette fonction s'appelle elle-même, jusqu'à ce que la valeur atteigne 1.
Une fois que la valeur en atteint une, la condition if est remplie et la partie return 1 est appelée, mettant fin complètement à la fonction (un peu comme le ferait un break;, pour le dire simplement), elle cessera donc d'exécuter le return factorial(value - 1) * value;
La valeur retournée ' 1 ' provient de cette expression
return factorial(value - 1) * value;
Et est utilisé uniquement ici, les lignes précédentes ne seront jamais évaluées.
Dans ce cas, la récursivité fonctionne de la même manière qu'une boucle. Pour comprendre comment cela fonctionne, vous pouvez utiliser le débogueur, ou essayer d'écrire chaque instruction (instruction, expression) dans l'ordre dans lequel elle sera évaluée.
Pour factorielle(3) cela ressemblera à ceci
factorial(3)
if(3==1) //false
factorial(2) //to return factorial(2) * 3 when function becomes evaluated
if(2==1) //false
factorial(1) // //to return factorial(1) * 2 when function becomes evaluated
if(1==1) //true
return 1;
return /*factorial(1) = */ 1 * 2;
return /*factorial(2) = */ 2 * 3; //return 6 - result of your top call of factorial(3) from the main call