Fonction De Fibonacci Question
J'était en train de calculer la suite de Fibonacci, et suis tombé sur ce code, j'ai vu beaucoup de choses:
int Fibonacci (int x)
{
if (x<=1) {
return 1;
}
return Fibonacci (x-1)+Fibonacci (x-2);
}
Ce que je ne comprends pas comment il fonctionne, en particulier la partie de retour à la fin: est-ce qu'il appel la fonction de Fibonacci à nouveau? Quelqu'un pourrait-étape de moi grâce à cette fonction?
Si vous avez de la difficulté à comprendre les fonctions récursives, un factorielle récursive peut être plus facile à démarrer avec. groups.engin.umd.umich.edu/CIS/course.des/cis400/cpp/...
Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité. Pour ce faire, rendez-vous ici: stackoverflow.com/questions/717725/understanding-recursion
Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité. Pour ce faire, rendez-vous ici: stackoverflow.com/questions/717725/understanding-recursion
if (x<2) return x;
OriginalL'auteur Dominic K | 2010-05-01
Vous devez vous connecter pour publier un commentaire.
Oui, la fonction s'appelle elle-même. Par exemple,
Noter que la fonction de Fibonacci est appelé 9 fois ici. En général, le naïf récursif de la fonction de fibonacci a exponentielle des temps de course, qui est généralement une Mauvaise Chose.
+1 pour des raisons de simplicité.
Notez que parce qu'elle est récursive, il s'exécute en temps exponentiel. Un algorithme itératif est plus efficace. En effet, j'ai été en mesure de calculer les 10 000 premiers nombres de fibonacci en quelques secondes. goo.gl/hnbF5
Ceci explique avec justesse et calcule l'erreur dans le code d'origine, à savoir que Fibonacci(0) doit être de 0, pas 1. Cette erreur (ce qui est fréquemment répétée à travers le net), il suffit de changements de la séquence d'un même endroit, les mêmes numéros sont retournés, à l'exception de l'manquant 0.
OriginalL'auteur dan04
C'est un exemple classique d'un fonction récursive, une fonction qui s'appelle elle-même.
Si vous le lisez attentivement, vous verrez qu'il va appeler lui-même, ou, recurse, encore et encore, jusqu'à ce qu'il atteigne la dite de la base de cas, quand
x <= 1
à quel point il va commencer à "la plage" et de résumer les valeurs calculées.Le code suivant clairement imprime la trace de l'algorithme:
Le résultat est le suivant:
Un arbre représentation de la trace ressemblerait à quelque chose comme
Les parties importantes à penser lors de la rédaction de fonctions récursives sont:
1. Prendre soin de la base de cas
Ce qui serait arrivé si nous avions oublié
if (x<=1) return 1;
dans l'exemple ci-dessus?2. Assurez-vous que les appels récursifs en quelque sorte diminuer vers la base de cas
Ce qui serait arrivé si nous avons accidentellement modifié l'algorithme de retour
fibonacci(x)+fibonacci(x-1);
Je suis entièrement d'accord avec vous. @dan04s réponse est sur place 🙂
+1 Voie pour aller de l'Idaho
fib 0 doit être de 0, pas 1.
OriginalL'auteur aioobe
C'est terriblement inefficace. Je suggère ce qui suit linéaire alternative:
La suite de fibonacci peut être exprimé de façon plus succincte dans les langages fonctionnels.
Comme un exercice intellectuel, ce qui est évidemment, vous auriez presque toujours envie de vous préoccuper de l'efficacité. L'important est bien de reconnaître la différence entre ce que vous avez trouvé et que FredOverflow et quelques autres sont en indiquant. Il y aura beaucoup de perspicacité dans ces réponses. Vous avez de la chance de chien.
OriginalL'auteur fredoverflow
C'est la fonction classique de la récursivité. http://en.wikipedia.org/wiki/Recursive_function devrait vous obtenir a commencé. Essentiellement, si x inférieur ou égal à 1, il se retourne 1. Sinon, il diminue x Fibonacci à chaque étape.
OriginalL'auteur Gabriel
Comme votre question est marqué C++, je me sens obligé de souligner que cette fonction peut également être réalisé au moment de la compilation comme un modèle, si vous avez une variable de compilation pour l'utiliser avec.
Été un moment depuis que j'ai écrit ces, de sorte qu'il pourrait être un peu, mais ça devrait être ça.
Non, il n'est pas. Modèle instanciations sont memoized.
OriginalL'auteur Puppy
Oui, la fonction de Fibonacci est appelée de nouveau, cela s'appelle de la récursivité.
Comme vous pouvez l'appeler une autre fonction, vous pouvez appeler la même fonction. Depuis fonction du contexte est empilé, vous pouvez appeler la même fonction sans déranger le cours d'exécution de la fonction.
Noter que la récursivité est difficile depuis que l'on pourrait appeler la même fonction encore infiniment et remplir la pile d'appel. Cette erreur est appelée un "Stack Overflow" (ici !)
OriginalL'auteur Vincent Robert
En C et la plupart des autres langues, une fonction est permis d'appeler lui-même, tout comme toute autre fonction. Ceci est appelé la récursivité.
Si cela semble étrange parce que c'est différent de la boucle que vous écrivez, vous avez raison. Ce n'est pas une très bonne application de la récursivité, parce que trouver le n ème nombre de Fibonacci nécessite deux fois plus de temps que de trouver les n-1, conduisant à des temps d'exécution exponentiel dans n.
Une itération sur la suite de Fibonacci, le souvenir de la précédente, le nombre de Fibonacci avant de passer à la prochaine améliore l'exécution linéaire dans n, la façon dont il devrait être.
La récursivité lui-même n'est pas terrible. En fait, la boucle que je viens de décrire (et une boucle) peut être mis en œuvre comme une fonction récursive:
OriginalL'auteur Potatoswatter
Ou si vous voulez être plus rapide, mais l'utilisation de la mémoire.
et pour n = 10 par exemple, vous aurez :
fib[1] fib[2] fib[3] fib[4] fib[5] fib[6] fib[7] fib[8] fib[9] fib[10]
1 1 2 3 5 8 13 21 34 55`
OriginalL'auteur Madalin Nitu