Evaluation des fonctions récursives, itératives et CPS
Application, bien évidemment, à la factorielle...
Version récursive :
(define (fac-rec n)
(if (zero? n)
1
(* n (fac-rec (sub1 n)))))
- L'évaluation de
(fac-rec n) se produit en deux phases : - une phase d'empilement des multiplications différées ;
- une phase de dépilement et d'évaluation de ces multiplications.
- La consommation de pile est linéaire.
Version itérative (récursive terminale) :
(define (fac-iter n)
(letrec ((iter (lambda (n acc)
(if (zero? n)
acc
(iter (sub1 n) (* n acc))))))
(iter n 1)))
- Cette deuxième version est syntaxiquement récursive (une fonction qui s'appelle elle-même), mais la récursivité est terminale (le résultat de la récursion est renvoyé sans traitement), autrement dit chaque appel à
iter est remplacé dans la pile par un autre. - Les calculs sont effectués à chaque étape à l'aide d'un accumulateur.
- La consommation de pile est constante.
Version CPS (Continuation Passing Style) :
(define (fac-cps n f)
(if (zero? n)
(f 1)
(fac-cps (sub1 n)
(lambda (x) (f (* n x))))))
- Itérative donc consommation de pile constante.
- Les calculs sont effectués par le biais de lambda-expressions "emboîtées".
- La consommation de mémoire nécessaire au stockage des ces lambda-expressions est linéaire.
- L'évaluation de
(fac-cps n) se fait en deux phases : - une phase de création de lambda-expressions
- une phase d'application des lambda-expressions.
- Pour simplifier la représentation de l'évaluation, on omet que ce sont en fait des fermetures qui sont créées (paires environnement+expression), et on résoud à la volée les références au compteur d'itérations.
