Comprendre le comportement Java en factorielle récursive
J'ai créé deux méthodes récursives pour calculer factoriel comme suit:
private int fact1(int n) {
if (n == 0 || n == 1)
return 1;
return n * fact1(--n);
}
private int fact2(int n) {
if (n == 0 || n == 1)
return 1;
return fact2(--n) * n;
}
Lorsque j'appelle fact1(4), il renvoie 24. Lorsque j'appelle fact2(4), il renvoie 6 (EDIT: ne renvoie pas 18 mais 6). Je sais que la deuxième méthode fait 3 * 2 * 1, mais je ne comprends pas pourquoi pas 4 * 3 * 2 * 1.
La même chose se produit si je change le retour en
//fact3(4) returns 60.
return (n + 1) * fact3(--n); // wrong
//fact4(4) returns 24
return fact4(--n) * (n + 1); // works
Pourquoi la méthode présente-t-elle ce comportement??
La question porte sur les différents comportements. Je sais n * fact(n-1) est le meilleur moyen de le résoudre.
Quelqu'un Peut-il m'aider à comprendre l'évaluation de cette expression? Merci!
1 answers
Tout se résume à la différence entre ces expressions:
return n * f(--n);
return f(--n) * n;
Lorsque n = 4, ces expressions sont évaluées comme ceci:
return 4 * f(3);
return f(3) * 3;
Parce que le moment --n est évalué, la valeur de n est diminuée de 1.
Voici comment fonctionne l'opérateur prefix --.
Cela pourrait aider à évaluer récursivement l'ensemble des expressions à la main. Le premier:
// first
return 4 * f(3);
return 4 * 3 * f(2);
return 4 * 3 * 2 * f(1);
return 4 * 3 * 2 * 1;
// second
return f(3) * 3;
return f(2) * 2 * 3;
return f(1) * 1 * 2 * 3;
return 1 * 1 * 2 * 3;
Sur une note connexe, devinez comment cela sera évalué:
return f(n--) * n;
Il va être:
return f(4) * 3;
, Car ici le suffixe -- opérateur est utilisé: -1 décrémenter sera appliqué après l'évaluation de n dans f(...).