Introduction
Récursion terminale
Une fonction est récursive terminale si la dernière chose exécutée par la fonction est un appel à elle-même.
Chaque fois qu'une fonction est appelée, un cadre de pile contenant ses variables locales et ses arguments est placé au sommet de la pile d'appels.
Quand une fonction renvoie, le cadre de pile est retiré de la pile.
Les fonctions récursives terminales permettent l'optimisation des appels terminaux (ou l'élimination des appels terminaux).
C'est une optimisation qui permet de réutiliser le dernier cadre de pile pour l'appel de fonction suivant, quand on sait que la fonction précédente n'en a plus besoin.
Cela limite le risque de débordement de la pile d'appels, une situation dans laquelle il y a tant de cadres sur la pile d'appels qu'il ne reste plus de mémoire pour en créer un de plus.
Optimisation des appels terminaux en Elm
Sous certaines conditions, le compilateur Elm est capable d'effectuer automatiquement une optimisation d'appel terminal lorsqu'il compile vers JavaScript.
L'optimisation peut se produire pour une fonction récursive quand la dernière opération d'une branche consiste à appeler la fonction elle-même dans une simple application de fonction.
Regardons quelques exemples :
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
L'implémentation ci-dessus n'est pas récursive terminale, car la dernière opération de la branche else est une multiplication n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
L'implémentation ci-dessus est récursive terminale et sera optimisée, car la dernière opération de la branche else est factorialHelper qui s'appelle elle-même.
Cela ne serait pas possible pour une fonction dont la signature de type est Int -> Int, et en pratique, l'optimisation des appels terminaux s'obtient souvent en définissant des fonctions auxiliaires.
Instructions
Piper est une pâtissière passionnée de tartes.
Personne ne sait si elle s'est mise aux tartes à cause de son nom, ou si elle a changé de nom pour qu'il colle à son passe-temps. À première vue, la seconde hypothèse semble peu probable, mais tu vois, Piper est absolument fascinée par les tartes. Elle bricole sans cesse dans la cuisine, ajuste ses recettes, améliore son art, au plus grand bonheur de ses amis.
Sa dernière passion ? Faire des tartes aussi rondes que possible, jusqu'à la perfection mathématique, avec l'aide de son nombre préféré, tu l'as deviné : π.
Piper a trouvé une formule élégante pour calculer π de manière itérative, la transformation de convergence de Newton/Euler :
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Aide Piper à préparer sa tarte mathématiquement parfaite en calculant π.
1. Factorielle
Échauffons-nous d'abord. L'opérateur factorielle, généralement noté !, est défini ainsi :
0! = 1
n! = 1 * 2 * 3 * ... * n
Définis la fonction factorial, qui calcule la factorielle de façon récursive terminale.
factorial 4
-- 24
2. Double factorielle
L'opérateur double factorielle, généralement noté !!, est défini ainsi :
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Définis la fonction doubleFactorial, qui calcule la factorielle de façon récursive terminale.
factorial 5
-- 15
factorial 6
-- 48
Définis la fonction pipersPi, qui approxime π en utilisant un nombre donné de termes de la formule de la transformation de convergence de Newton/Euler, de façon récursive terminale.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Calculons ensemble le premier terme. Pour une limite supérieure de 0 (au lieu de l'infini), on obtient :
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Chaque terme supplémentaire améliore l'approximation.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Exercice d'apprentissage
