J'ai lu sur la récursivité et je suis très intéressé à comprendre une chose très basique que j'utilise dans la factorielle. Depuis que j'ai bien fait des recherches à ce sujet, vu des vidéos particulières, mais d'une manière ou d'une autre, cette chose me déroute beaucoup. J'ai la possibilité d'écrire le mug un code et d'avancer, mais j'apprends bien les choses.
Voici les sources de la récursivité:
J'ai une chose à demander car dans le code j'ai vu une chose qui est le if-else . Je sais très bien si autre condition. Mais ici, les choses sont un peu compliquées.
public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}
Dans le code ci-dessus, ici le résultat semble être correct mais ce que je pense, c'est pourquoi il ne renvoie pas seulement 1 quand il satisfait la condition, et comment se fait-il imprime le résultat correct. Il y a un seul hic que je n'ai pas pu saisir. Aidez-moi à surmonter ça.
Considérez-moi comme un apprenant dans le domaine du codage. Merci
7 Réponses :
Un simple essai à sec vous conduirait à votre réponse. N est soustrait par un à chaque fois jusqu'à ce qu'il atteigne 1.
Par exemple, considérons N comme 4
Cela irait dans l'instruction else, qui deviendrait return 4 * fact (4-1)
La récursivité a maintenant 4 * fact (3)
le fait 3 conduirait à 3 * fact (2)
Ce qui équivaudrait à ce que la première équation soit égale à 4 * 3 * fact (2) ;
Cela se produit jusqu'à ce que N devienne 1, donc l'équation entière serait comme 4 * 3 * 2 * 1
à 1, la récursivité s'arrête et nous commençons à revenir par la pile de récursivité.
J'espère que cela clarifie votre question.
Le retour de la pile de récursivité était la capture Je pensais qu'il devait simplement renvoyer 1, mais il le stockait en fait dans la pile, les résultants jusqu'à ce qu'il atteigne 1.
Bonjour, camarade apprenant le code, j'espère que les gens sur StackOverflow auront pitié de votre question, car ils n'en ont jamais eu avec mes questions.
Quoi qu'il en soit, parcourons votre code et voyons ce qui se passe exactement:
je vais appeler "fact (5) "dans ma main. Ce qui suit est une représentation de ce qui se passe en arrière-plan:
//fact(1) = 1
public static int fact(2){ //returns the else case, 2*1 = 2 so fact(2) = 2
if(2 <= 1)
return 1;
else
return 2 * 1;
}
public static int fact(3){ //same here, fact(2) = 2, so we end up with 3*2 = 6
if(3 <= 1)
return 1;
else
return 3 * 2;
}
public static int fact(4){
if(4 <= 1)
return 1;
else
return 4 * 6; //fact(3) = 6, so we return 4*6 = 24
}
public static int fact(5){
if(5 <= 1)
return 1;
else
return 5 * 24; //fact(4) = 24, so we return 5*24 = 120
}
et le fait 4 sera:
public static int fact(3){
if(3 <= 1)
return 1;
else
return 3 * fact(2);
}
public static int fact(2){
if(2 <= 1)
return 1;
else
return 2 * fact(1);
}
public static int fact(1){
if(1 <= 1) //true for the first time
return 1;
else
return 1 * fact(0);
}
et ainsi de suite:
public static int fact(4){
if(4 <= 1)
return 1;
else
return 4 * fact(3);
}
dans "fact (1)" le cas if se déclenche pour la première fois, et il renvoie 1. Si nous remontons maintenant:
public static int fact(5){
if(5 <=1)
return 1;
else
return 5 * fact(4);
}
J'espère que cela vous aidera à clarifier votre question.
il y a une erreur dans votre dernière boucle récursive si (4 <= 1)
et dieu merci, vous avez donné un avis, la plupart des gens me dénonceraient simplement pour "informations trompeuses" sur ce site ces jours-ci
Salut @Alan, il n'y a rien à craindre si vous ne parvenez pas à obtenir des commentaires positifs ici / n'importe où. C'est juste l'art d'apprendre à demander ou à répondre. Je peux voir vos efforts dans votre réponse, et c'est formidable. Tout ce que vous avez à apprendre est de savoir comment demander maintenant. J'ai été banni de StackOverflow trois fois, je n'ai jamais abandonné et je vois maintenant que cela me donne des résultats. Merci pour la contribution Alan :) Heureux que vous essayiez.
Ouais, tout ce que tu as dit est vrai. Je n'ai qu'un seul problème. Qu'il y a des utilisateurs qui se dépassent au-dessus de vous et exploitent leurs provinces. C'est quelque chose que je ne peux pas autoriser sur ce site.
Ils reprochent à quelqu'un de poser des questions simples. Ils vous interdisent de poser des questions, ce qui devrait plutôt être encouragé que découragé, même si la question est stupide, même si elle est trop large, même si elle est hors sujet. Interdisez ceux qui traînent, pas ceux qui ont soif de connaissances
Je pense que la meilleure façon de comprendre cela est un exemple. Par exemple, si vous appelez fact (3), l'exeuction de code serait comme ceci (sous forme de pseudocode):
fact (3)
return 3 * 2 ---> This give 6, and it is the final result of fact(3)
fact (2)
return 2 * 1 --> 2 this will be the result of fact(2)
fact(1)
1 is same as 1 so return 1 ---> 1 will be the result of fact(1)
Revenons maintenant au fait (2)
2 is greater than 1 so return 2 * fact(1) ---> Lets wait for this
Revenons maintenant au fait (3)
3 is greater than 1 so return 3 * fact(2) ---> Lets wait for this
Salut, merci pour votre contribution, mais votre méthodologie est erronée. Tout d'abord, le fait (3) est 6, pas 9. Deuxièmement, si vous suivez la pile, alors fact (1) -> fact (2) -> fact (3). Veuillez le corriger, sinon cela donnerait une mauvaise idée à ce sujet.
Super, j'apprécie votre coopération à ce sujet. Je vais maintenant supprimer mon vote défavorable. Cela aidera les codeurs qui viendront dans un proche avenir à apprendre comme moi :)
La récursivité est utilisée lorsque vous pouvez diviser votre tâche en petites tâches similaires. Et tirez parti de cela pour accomplir une tâche importante. Comme dans ce cas, la factorielle du nombre peut être représentée par le nombre multiplié par la factorielle de (nombre-1) jusqu'à ce qu'elle devienne 1. où la factorielle de 1 et 0 est 1.
Donc
C'est la raison pour laquelle if clause handle
public static int fact(int n) {
if (n <= 1) {
// if a number is 1 or less than on then factorial will be 1
return 1;
}
else {
/*this part will execute only of number is greater than 1, ex 2,3
* According to factorial logic, factorial of a number n will be (n * factorial of (n-1))
* Ex: factorial of 2 = 2*1
* factorial of 3 = 3*2*1
* factorial of 4 = 4*3*2*1
*/
return n * fact(n - 1);
}
}
La visualisation d'une fonction récursive sous forme d'arborescence la rend beaucoup plus facile à comprendre pour les débutants. Chaque fonction récursive fonctionne en deux étapes:
Étape 1 : développement de l'arborescence
Étape 2 : substitution arrière
Considérez l'image ci-dessous. Dans l'image, la couleur rouge indique l'étape 1 et la couleur verte montre l'étape 2. Vous ne pouvez pas effectuer l'étape 2 tant que l'étape 1 n'est pas terminée. C'est la raison pour laquelle vous devez avoir une condition de terminaison dans chaque fonction récursive sinon; l'arborescence continuera d'étendre votre programme manquera de mémoire.
Lorsque vous avez appelé fact (4) , il s'est développé en 4 * fact (3) qui s'est développé comme indiqué ci-dessous:
fact(4) = 4 * fact(3) fact(3) = 3 * fact(2) fact(2) = 2 * fact(1) fact(1) = 1
Maintenant, tout vous devez faire est de remplacer les valeurs afin d'obtenir la valeur de fact(4).
Sur le matériel, la fonction récursive se développe comme l'arbre montré ci-dessus. Cela se produit sur la pile et chaque nœud de l'arborescence est un enregistrement d'activation. Consultez cette réponse pour en savoir plus sur l'enregistrement d'activation .
La fonction récursive est une fonction qui s'appelle d'elle-même
Elle permet aux programmeurs d'écrire des programmes efficaces en utilisant une quantité minimale de code .
L'inconvénient est qu'ils peuvent provoquer des boucles infinies et d'autres résultats inattendus s'ils ne sont pas écrits correctement .
Pour écrire une fonction récursive.
Le premier point à considérer est quand devez-vous décider de sortir de la boucle qui est la boucle if
Le deuxième est le processus à faire si nous sommes notre propre fonction
De l'exemple donné:
public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}
De l'exemple ci-dessus
public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}
Est le facteur décisif quand sortir de la boucle
public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}
Est-ce que le traitement réel doit être fait
Permettez-moi de casser la tâche une par une pour une meilleure compréhension. >
Voyons ce qui se passe en interne si je lance fact(4)
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
Si la boucle échoue, elle va donc à la boucle else
donc il renvoie 4 * fact (3)
Dans la mémoire de la pile, nous avons 4 * fact (3)
Remplacement de n = 3
else
return n * fact(n-1);
Si la boucle échoue, elle va donc dans la boucle else
donc elle renvoie 3 * fact (2)
Rappelez-vous que nous avons appelé `` 4 * fact (3) ''
Le résultat de fact (3) = 3 * fact (2)
Jusqu'à présent, la pile a 4 * fact (3) = 4 * 3 * fact (2)
Dans la mémoire de la pile, nous avons 4 * 3 * fact (2)
Remplacement de n = 2
if(n <=1)
return 1;
Si la boucle échoue, elle va donc dans la boucle else
donc elle renvoie 2 * fact (1)
Rappelez-vous que nous avons appelé 4 * 3 * fact (2)
La sortie pour fact (2) = 2 * fact (1)
Jusqu'à présent, la pile a 4 * 3 * fact (2) = 4 * 3 * 2 * fact (1) code>
Dans la mémoire de la pile, nous avons 4 * 3 * 2 * fact (1)
Remplacement de n = 1
public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}
Si la boucle est vraie
donc elle renvoie 1
N'oubliez pas que nous avons appelé 4 * 3 * 2 * fact (1)
La sortie pour fact (1) = 1
Jusqu'à présent, la pile a 4 * 3 * 2 * fact (1) = 4 * 3 * 2 * 1
Le résultat de fact (4) = 4 * 3 * 2 * 1 = 24
Alok, Disons que vous passez 3 et que la première itération attend maintenant le résultat de l'appel de fonction. Maintenant, cet appel déclenche un autre appel et il attend le résultat. Enfin, quand il est 1, renvoie 1 et cet appel a la réponse et donc il se multiplie et renvoie le résultat. Ainsi, le retour atteint finalement le premier appel en attente et la réponse finale est renvoyée. De la manière la plus simple, vous avez appelé une personne (a) et cette personne a appelé une autre personne (b) et cette personne a appelé une autre personne (c) qui lui a donné une réponse. Maintenant que c a donné une réponse, b traite cette réponse et la donne à un qui à son tour traite cette réponse et vous la rend. C'est la raison pour laquelle vous avez obtenu une réponse correcte au lieu de 1 dans le programme récursif. J'espère que vous l'avez compris.
Merci Vino V
Vous devriez connaître le terme de pile. Par exemple, lorsque vous appelez func (3), cela ressemble à ceci: 3 * func (2), puis func (2) est appelé et renvoyé sous la forme 2 * func (1) et tous ces appels sont empilés et lorsque le cas de base est atteint, ils sont sorti de la pile, donc func (1) renvoie 1 donc func (2) renvoie 2 * 1 et func (3) retourne 3 * 2 = 6