Stupé sur cet exemple de code BAD C ++ dans un article de blog, sans explication de la raison pour laquelle il est considéré comme "mauvais". J'ai mes propres idées, mais j'aimerais entendre expérimenté C ++ Devs à ce sujet.
unsigned int Fibonacci (unsigned int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}
5 Réponses :
Peut-être parce qu'il fonctionne dans une période exponentielle?
Et c'est beaucoup trop de lignes de code pour cette méthode particulière: retour (n <2)? N: Fibonacci (N-1U) + Fibonacci (N-2U); sur une autre note, le problème principal avec l'équation de la forme fermée est que cela conduira probablement à des erreurs de points flottants.
Plus important encore, il consomme une mémoire exponentielle de la pile de processeur (en raison de la profondeur exponentielle de la récursion). C'est mauvais parce qu'il ne fonctionne que pour de petits nombres d'entrée. Pour des nombres plus importants, il se bloque à cause du débordement de pile.
Ne devrait pas être la mémoire exponentielle de la pile, car C ++ ne parle pas automatiquement. Donc, vous n'obtiendrez pas plus que O (n) la taille de la pile.
@Steve Wang: O (n) = O (exp (C * Tailleof (n))) est Taille de la pile exponentielle. Bien que bon point depuis que je viens de comprendre que le temps de fonctionnement est O (2 ^ n) = O (exp (c * n)) = O (exp (C * exp (C1 * Tailleof (N))) qui réellement extrêmement super exponentielle. Juste horrible. :)
Si vous le calculez en fonction du nombre de bits en n, la taille de la pile exponentielle. Mais je pense que tout le monde appelle ceci O (n).
Élaborer sur la déclaration ci-dessus: puisque vous ne souhaitez pas mémoter, vous appartenez 2 processus avec le premier appel, et chacun de ces deux procédés, et ainsi de suite dans la chaîne jusqu'à ce que vous appuyiez sur le boîtier de base.
Trois façons d'éviter ceci: 1) Memoize, 2) Faites-le itérativement, ou 3) Utilisez l'équation de forme fermée pour la séquence Fibonacci. : D
+1 Bien que ce ne sont pas processus au sens littéral, bien sûr.
Hé bien oui. Ils sont plus des processus dans le sens où un "processus récursif" est un processus.
Whoah. Merci d'avoir utilisé le terme "mémoialisation". J'ai appris un nouveau mot aujourd'hui. :)
Certaines personnes diront que c'est mauvais, car il utilise la récursion ou parce qu'il l'utilise sans mémoisation, ce qui est assez raisonnable car il existe des approches qui utilisent uniquement une itération et d'enregistrer des valeurs qui seraient répétées dans des variables auxiliaires, d'autres souligneront le fait qu'il peut être calculé à l'aide de la formule de Binet, à un certain degré de précision.
D'autres personnes diront que ce sont les points de retour multiple, et même plus étrangement, quelqu'un pourrait dire que c'est mauvais parce que l'autre est superflu et qu'elle pourrait être retirée pour sauver une ligne.
La plupart des valeurs de fibonnacci (n) sont calculées deux fois.
Par exemple, Fibonacci (5) appelle Fibonacci (4) et Fibonacci (3) .
que fibonacci (4) appelle à tour les appels fibonacci (3) et fibonacci (2).
Voyez comment Fibonacci (3) dans cet exemple est appelé deux fois? C'est là que la mémoire Memoize aiderait, mais l'algorithme, tout en intéressant et récursif, n'est pas efficace. Il serait préférable d'utiliser un algorithme plus efficace que de mémoiser une inefficace.
heure de fonctionnement exponentielle (et peut être même super-exponentielle - comme dans ce cas) est supportable si vous avez une éternité à attendre jusqu'à la fin du programme.
Mais rien dans le monde ne peut éventuellement gérer la consommation de mémoire exponentielle - en particulier la consommation de pile de programme exponentielle (en raison de la profondeur exponentielle de récursion). Ce programme va simplement planter à cause d'un débordement de pile avec un numéro d'entrée suffisamment important.
Ce n'est pas comme "la récursion est diabolique".
La récursion est acceptable si la profondeur de la récursion est limitée par une petite valeur (par exemple, si elle est logarithmique de la taille d'entrée ou non de Tailleof (int) ou de quelque chose). Mais pas lors de la proportionnelle à la valeur d'entrée n .
Vous devez supprimer "C ++" de cette question. Cet algorithme transcende vraiment les langues, c'est mauvais avec toute mise en œuvre !
@Tom, vrai, mais il y a probablement des langues fonctionnelles qui optimiseraient probablement cela tout simplement bien. Je me souviens quelques-uns quelques mémoations automatiques.