Skip to content

2 4 5 traduction

Traduction de fonction récursive en fonction itérative

Toute récursivité peut plus ou moins facilement être traduite en fonction non récursive.

Dans le cas de récursivité terminale (tail recursion), c'est-à-dire où la dernière action de la fonction consiste en un appel récursif, il est assez simple de remplacer la récursivité par une boucle while.

C'est le cas pour les codes donnés dans ce module test_syracuse, recherche_dichotomique.

Dans le cas où le traitement est uniquement un post-traitement, il est possible de prendre le code à "l'envers", c'est-à-dire de traduire le code en boucle qui fait le traitement de base, suivi du post-traitement pour n valant 1 ensuite pour n valant 2, ... jusqu'à avoir traité le cas pour la valeur n initiale. C'est ce qui se passe pour le code non récursif de la factorielle.

Quand la fonction a plusieurs appels à des instances plus petites ou qu'il y a à la fois un pré-traitement et un post-traitement, il est plus difficile de supprimer la récursivité et cela ne peut souvent être fait qu'avec une pile (stack) simulant cette récursivité.