Je traverse un livre de programmation et l'un des exemples concerne les numéros de Fibonacci et la façon dont une fonction récurrente trouve le numéro Fibonacci pour le NTH un.
Le code ressemble à ceci: Ce n'est pas exact car je tape de mon téléphone et j'ai une compréhension comment le code fonctionne, c'est S'approcher jusqu'à ce qu'il renvoie 1, il ajoute les valeurs de retour jusqu'à ce que vous ayez le numéro Fibonacci correct pour la position dans la séquence. Donc, je n'ai pas besoin d'aide avec le code. Ce que j'ai besoin d'aide pour comprendre pourquoi cela fonctionne. Comment l'ajout de tous les retours donne-t-il la bonne réponse? S'il vous plaît quelqu'un peut-il expliquer pourquoi cela fonctionne. Merci. Cela me rend fou.
9 Réponses :
Un numéro de Fibonacci est défini comme la somme des deux numéros de fibonacci précédents. Qui sont chacun définis comme la somme des deux nombres précédents fibonacci. Etcetera, etcetera, jusqu'à ce que vous atteigniez 1. Comprenez? Tout numéro de fibonacci aléatoire peut être défini comme la somme de deux nombres Fibonacci; Ceux-ci peuvent être définis de manière récursive comme la somme de deux numéros de Fibonacci, etc., la définition d'un numéro de fibonacci est fondamentalement récursive; C'est-à-dire la définition de cela implique ce qu'il définit.
Ce truc peut être délicat, mais il est très fondamental de comprendre la récursion et la science informatique. Continuer à travailler dessus; Ça cliquera éventuellement.
Comment vient nous faire N-1 + N-2? Je ne fais pas la connexion de la façon dont la prise de 1 ou 2 et que répétez découvre le numéro de Fibonacci correct.
@Joseph, la définition d'un numéro de fibonacci (n) est qu'il s'agit de la somme des deux numéros de Fibonacci précédents (N - 1, N-2). Vous ne prenez pas 1 ou 2 du nombre lui-même; Vous allez en arrière dans la séquence de chiffres qui composent les numéros de Fibonacci. Si votre numéro de fibonacci (n) a 13 ans, le numéro Fibonacci (N-1) est 8, pas 12.
Je suggérerais de comprendre comment la récursion fonctionne. Fondement la fonction FIB s'exécute à un argument plus petit jusqu'à ce que l'argument soit descendant à 2, puis il vient juste de retourner 1.
fib(1) = 1 fib(2) = 1 fib(3) = fib(2) + fib(1) = 1 + 1 = 2 fib(4) = fib(3) [ fib(2) + fib(1) = 1 + 1 = 2 ] + fib(2) = 2 + 1 ...
En fait, l'OP a déclaré qu'il comprenait bien la récursion. Il ne peut tout simplement pas comprendre pourquoi la fonction récursive peut générer des numéros de fibonacci. Je suppose que l'OP ne comprend pas les numéros de Fibonacci ou une compréhension de "manuel" (c'est-à-dire s'il est demandé, il peut vous dire que c'est la somme de deux numéros de fibonacci précédents mais ne comprend pas ce que cela signifie vraiment, mais pas voir Que c'est vraiment la réursion. Ceci est juste assez pour passer des examens, mais malheureusement pas assez pour l'appliquer dans la vie réelle).
Un numéro Fibonacci est défini comme la somme des deux numéros de fibonacci précédents. Cela donne ce qui suit: donc pour le 3ème nombre (1 1 2 ), vous obtiendriez le résultat de la recherche de la précédente - c'est-à-dire 2e (1 1 2) Number et l'ajoutez-le au numéro avant le précédent - c'est-à-dire 1er ( 1 1 2). Vous devez également comprendre que le programme a besoin de Pour calculer la valeur des deux numéros précédents avant de pouvoir calculer le numéro que vous souhaitez connaître. Par conséquent, il continue à s'appeler - en utilisant la même méthode - jusqu'à ce qu'il ait tout calculé.
Tout le monde a vraiment aidé mais votre explication a fait cliquer sur. Santé mec
Récursion est comme ceci:
Par définition, les numéros Fibonacci sont la somme des deux numéros précédents de la série (où les deux premières sont 0 et 1).
Ainsi, lorsque vous obtenez le numéro Fibonacci à un endroit, vous pouvez le ré-écrire comme la somme des deux numéros de Fibonacci précédemment.
Utilisation de la récursion, vous passez à travers ce processus jusqu'à ce que les "numéros de Fibonacci précédemment" sont 1 et 1 (dans le cas de cet algorithme), puis procédez à ajouter les numéros ensemble "sauvegarder" la récursivité jusqu'à ce que vous obtenez Retour à votre emplacement d'origine dans la séquence.
C'est la définition des numéros de fibonacci.
N-ème numéro de Fibonacci renvoie la somme des numéros (N-1) TH et (N-2) TH Fibonacci.
Nous pouvons donc prouver par un raisonnement inductif que, si FIB (N-1) et FIB (N-2) donnent le numéro valide (N-1)-et (N-2) - Numéro de fibonacci, FIB (N ) = FIB (N-1) + FIB (N-2) sera le numéro valide N-ème Fibonacci.
L'étape de base est que FIB (1) et FIB (2) sont correctes (c'est une fibe (1) = FIB (2) = 1) ...
Y a-t-il un moyen plus facile d'expliquer cela? C'est le problème que je suis coincé avec. Je ne peux tout simplement pas envelopper ma tête autour de ça
Qu'est-ce qui ne vous est pas clair? FIB (N) est FIB (N-1) + FIB (N-2) par définition. Cela signifie que le N-ème numéro de Fibonacci est (égale) la somme des deux numéros de Fibonacci précédents. - C'est comme dire: le n-ème nombre naturel est (égal) le (n-1) -th + 1; Le septième nombre naturel (c'est-à-dire: 7) est de 6 + 1. C'est la définition des nombres naturels
Le truc sur la compréhension de la récursion consiste à comprendre la pile.
Je suis à la ligne 2 dans une fonction appelée i puis appelez sur la ligne 4 de et cela le fait encore et encore lorsque la fonction est appelée de manière récursive. La pile grandit jusqu'à ce que quelque chose retourne, à quel point, à la ligne 2 de finalement, vous finissez par revenir dans la fonction d'appel (ou obtenez un trop-plein de pile car il pousse trop grand). La chose essentielle à retenir est que chaque fois que la fonction est appelée, elle reçoit une nouvelle image de pile contenant toutes vos variables locales et votre position précédente est enregistrée. C'est la récursion. Le problème principal est que, dans l'enseignement des personnes à la récursivité, tout le monde utilise toujours la séquence Fibonacci, ce qui signifie avoir deux appels de fonction récursive sur une ligne. Ceci est inutilement déroutant, car je suis sûr que vous serez d'accord! principale , toutes mes variables locales sont stockées dans mon cadre de pile: fib (3) , de sorte que l'ordinateur appuie ma position actuelle (EIP) à la pile, puis crée un nouveau cadre de pile pour FIB et ajoute ça aussi. Je ne peux jamais accéder que le châssis de pile haut: fib , il appelle fib à nouveau, Donc, la même chose arrive à nouveau: FIB , il renvoie 1. Ceci apparaît sur le cadre de pile haut et le rejette, il renvoie ensuite l'exécution au pointeur d'exécution enregistré et au programme Continue où il est laissé sur
Ce tutoriel vidéo devrait vous donner une meilleure image de la réursion de Fibonacci
[link] http: / /www.schooltrainer.com/study-material/computer-science/stepping-fibonacfunction.html
Si vous demandez cela, cela doit être parce que vous ne comprenez pas (a) la récursion ou (b) de la série Fibonacci. Qu'est-ce que c'est?
Google.com/search?q=recursion :-)
Je comprends comment le code fonctionne et comprend ce que sont les numéros de Fibonacci. Je reçois aussi que la réursion se passe parce que la fonction s'appelle-t-elle, je ne peux tout simplement pas comprendre pourquoi son travail.