Au début, on parlait du fait que certains langages détectaient les récursions terminales et les optimisaient.
L'exemple de la factorielle est justement un exemple de récursion terminale et certains compilos optimisent automatiquement. C'est donc joli ET efficace.
Maintenant, certains programmes récursifs ne sont pas récursifs terminal. Le compilo ne va pas optimiser mais de toute façon, ça serait dur de le faire.
Un bon exemple de ça, c'est les tours de Hanoï.
La procédure récursive, c'est
déplacer la pile de taille n-1 du pilier 1 sur le pilier 2
déplacer le cercle n du pilier 1 sur le pilier 3
déplacer la pille de tailler n-1 du pilier 2 sur le pilier 3
C'est pas récursif terminal mais c'est joli.
Traduire ça en impératif, c'est pas beau et même si on peut le faire, on obtient un truc aussi lent que la version récursive.
Oui, je sais, si on étudie le mouvement du cercle de taille 1, on peut ausi le faire impérativement mais là, on change complètement d'algorithme.
[^] # Re: sonntag
Posté par fmaz fmaz . En réponse à la dépêche Lisaac 0.12 en GPL v3. Évalué à 2.
L'exemple de la factorielle est justement un exemple de récursion terminale et certains compilos optimisent automatiquement. C'est donc joli ET efficace.
Maintenant, certains programmes récursifs ne sont pas récursifs terminal. Le compilo ne va pas optimiser mais de toute façon, ça serait dur de le faire.
Un bon exemple de ça, c'est les tours de Hanoï.
La procédure récursive, c'est
déplacer la pile de taille n-1 du pilier 1 sur le pilier 2
déplacer le cercle n du pilier 1 sur le pilier 3
déplacer la pille de tailler n-1 du pilier 2 sur le pilier 3
C'est pas récursif terminal mais c'est joli.
Traduire ça en impératif, c'est pas beau et même si on peut le faire, on obtient un truc aussi lent que la version récursive.
Oui, je sais, si on étudie le mouvement du cercle de taille 1, on peut ausi le faire impérativement mais là, on change complètement d'algorithme.