C'est exactement la méthode de "sioux" que j'ai eu la flemme de poster ici, tu stocke les résultats des appels intermédiaires dans une hash table, ce qui réduit le nombre d'appel récusifs de ~2^n à quasiment ~2*n
Le problème, c'est que ce genre d'optimisation est envisageable dans une librairie système, ou un programme de calcul lourd, mais dans la vie de tous les jours au boulot, tu programmes de manière naïve (il faut maintenir le code après, et les optimisations rende le déroulement du programme moins lisible).
D'autant plus que la meilleure optimisation dans ce cas là est de transformer l'appel récursif en boucle -> gain de vitesse ET de mémoire.
Alors que ton exemple permet de gagner en vitesse, mais au détriment de la mémoire (et encore ça se discute, moins de pile à gérer)
Le principe de la table de hash pour stocker les résultats intermédiaires d'appels récursifs est quand même une trés bonne solution en général.
[^] # Re: Comment casser le mythe de rapidité de Fibonacci :-)
Posté par darkleon . En réponse à la dépêche Erlang/OTP R11B supporte les architectures multiprocesseur. Évalué à 4.
Le problème, c'est que ce genre d'optimisation est envisageable dans une librairie système, ou un programme de calcul lourd, mais dans la vie de tous les jours au boulot, tu programmes de manière naïve (il faut maintenir le code après, et les optimisations rende le déroulement du programme moins lisible).
D'autant plus que la meilleure optimisation dans ce cas là est de transformer l'appel récursif en boucle -> gain de vitesse ET de mémoire.
Alors que ton exemple permet de gagner en vitesse, mais au détriment de la mémoire (et encore ça se discute, moins de pile à gérer)
Le principe de la table de hash pour stocker les résultats intermédiaires d'appels récursifs est quand même une trés bonne solution en général.