Les exemples pourraient être implémentés avec de simple fonctions récursives dans un langage impératif. Où est la différence ?
si tu décides par exemple de calculer factorielle n en impératif tu feras quelque chose comme
fact <- 1
pour i = 1..n faire
fact <- fact * i
fait
retourne fact
En mémoire c’est constant (tu n’as que deux variable fact et i)
En récursif tu aurais quelque chose comme :
fact(0) = 1
fact(n) = n * fact(n-1)
Le problème c’est que la pile grandit beaucoup car en pratique, l’ordinateur déplie le calcul fact(fact(fact...fact(0)))) et quand il y a beaucoup d’appel récursif tu as un débordement de piles.
Maintenant dans certain cas, tu peux optimiser un appel récursif, le compilateur le transformant en boucle while. Pour cela il faut que ton code soit récursif terminale. Exemple :
Tu remarques que avec cette écriture, la dernière opération que fait la fonction fact est de s’appeler elle-même (alors que dans l’exemple précédant elle faisait un multiplication après). Dans le cas d’un compilateur d’un langage fonctionnel digne de ce nom, tous les fonctions avec appel récursif terminal sont automatiquement optimisées en boucle par le compilateur.
Donc pour résumé, la récursion est optimisés (dans certain cas) dans les langages fonctionnelles et pas chez les langages impératifs.
Cette histoire de récursion terminal est LE point important de la gestion mémoire des programmes fonctionnelles ; toute fonction non terminale est à bannir dans le cas où les appels récursifs sont nombreux. Mais vu que chaque boucle while peut être implémenter en tant que fonction récursives avec appel terminal, on ne perd aucune expressivité par rapport aux langages impératifs.
[^] # Re: C'est pourtant évident.
Posté par Diagonale de Cantor (site web personnel) . En réponse à la dépêche Coder efficacement, bonnes pratiques et erreurs à éviter. Évalué à 6. Dernière modification le 18 avril 2014 à 23:33.
si tu décides par exemple de calculer factorielle n en impératif tu feras quelque chose comme
En mémoire c’est constant (tu n’as que deux variable
facteti)En récursif tu aurais quelque chose comme :
Le problème c’est que la pile grandit beaucoup car en pratique, l’ordinateur déplie le calcul
fact(fact(fact...fact(0))))et quand il y a beaucoup d’appel récursif tu as un débordement de piles.Maintenant dans certain cas, tu peux optimiser un appel récursif, le compilateur le transformant en boucle while. Pour cela il faut que ton code soit récursif terminale. Exemple :
Tu remarques que avec cette écriture, la dernière opération que fait la fonction
factest de s’appeler elle-même (alors que dans l’exemple précédant elle faisait un multiplication après). Dans le cas d’un compilateur d’un langage fonctionnel digne de ce nom, tous les fonctions avec appel récursif terminal sont automatiquement optimisées en boucle par le compilateur.Donc pour résumé, la récursion est optimisés (dans certain cas) dans les langages fonctionnelles et pas chez les langages impératifs.
Cette histoire de récursion terminal est LE point important de la gestion mémoire des programmes fonctionnelles ; toute fonction non terminale est à bannir dans le cas où les appels récursifs sont nombreux. Mais vu que chaque boucle while peut être implémenter en tant que fonction récursives avec appel terminal, on ne perd aucune expressivité par rapport aux langages impératifs.