La programmation fonctionnelle avec Scala
La récursions
Il n'y a pas de variables modifiables en fonctionnel, il n'y a donc pas de boucles. À la place il convient d'utiliser les fonctions récursives. Il est important de se souvenir de la propriété suivante :
Propriété Tout algorithme utilisant une boucle peut être écrit avec des fonctions récursives
Récursivité terminale
Une fonction récursive terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. C'est à dire une fonction qui n'effectuve pas d'opération en remontant la pile d'appel.
Tandis qu'une fonction non terminale garde des valeurs intermédiaires dans la pile d'appel (ce qu'il faut éviter).
Par exemple cette version de la fonction factorielle est non terminale. On observe que l'appel récursif est multiplié par n :
Il est important d'écrire autant que possible des fonctions récursives terminales. Les fonctions récursives terminales sont mieux optimisées par le compilateur qui les transforme en boucle.
Pour cela on utilise couramment une astuce de programmation : les accumulateurs. Un accumulateur est une variable qui contient les valeurs déjà connues ou calculées. Il est passé en paramètre et généralement modifié à chaque appel de la fonction par elle-même pour être finalement utilisé au cas d'arrêt de la récursion.
Quand il est nécessaire de garder une signature de fonction sans accumulateur on utilise une fonction chapeau pour le masquer. C'est une fonction «vide» se contentant d'appeler la fonction récursive avec un paramètre d'initialisation pour l'accumulateur.
Exemple voici la fonction factorielle avec accumulateur et fonction chapeau (fac) :
