mars
2008
Un article de djo.mos
On connait déjà tous la récursion ou récursivité, qui consite à ce qu’une méthode s’appèle elle même dans son code, eventuellement avec des paramètres différents.
Cette technique permet de résoudre élégamment des problèmes complexes, comme par exemple le calcul de factorielles.
La définition mathématique d’une factorielle est:
n! = n*(n-1)*(n-2)*…*1
Ceci peut être exprimé en Java de cette façon:
Java:
public long fact(long n) {
return n <= 1 ? 1 : n * fact(n - 1);
}
Joli, n’est ce pas ?
Seulement, ça sature la capacité du type long dès que n>=21 :
fact(20)=2432902008176640000
fact(21)=-4249290049419214848
On peut dès lors passer par un type de capacité plus grande, telque le BigDecimal
Java:
public BigDecimal fact(BigDecimal n) {
return n.compareTo(BigDecimal.ONE) <= 0 ? BigDecimal.ONE : n
.multiply(fact(n.subtract(BigDecimal.ONE)));
}
C’est beaucoup moins joli (merci l’API géniale de BigDecimal) mais ça a le mérite de supporter des valeurs beaucoup plus volumineuses:
fact(21)=51090942171709440000
:
:
fact(5829)=un nombre astronomique que la console d’eclipse n’arrive pas à afficher :-O
fact(5830)=Kaboum ! java.lang.StackOverflowError !
Plus de mémoire stack pour appeler une méthode.
Ce n’est qu’un exemple parmi tant d’autres, et on aurait pu épuiser le stack beaucoup plus tôt avec d’autres exemple.
C’est la limitation principale de la récursivité: le Stack.
Pour expliquer, je vais dérouler l’exécution de la fonction fact:
fact(5830)
=> 5830 * fact(5829)
=> 5830 * 5829 * fact(5828)
=> 5830 * 5829 * 5828 * fact(5827)
:
:
à chaque itération, la JVM doit empiler les paramètres de la fonction fact (n, ainsi que d’autres données) dans la pile, et y passer la main tout en gardant une trace des résultats intermédiaires de l’itération courante.
C’est ainsi qu’avec un nombre raisonablement grand d’itération, on sature la pile.
Pour résoudre ce problème, on peut bien sûr passer par la méthode itérative (toute fonction récursive admet une version itérative).
Mais on peut aussi le résoudre autrement, tout en gardant l’aspect récursif. Autrement, les langages fonctionnels resteraient une théorie sur le papier.
La solution s’appèle la tail récursion, qui est une forme particulière de la récursion ordinaire.
Une fonction est est tail-récursion si elle s’appèle elle même dans son corps, sans aucune autre opération, eventuellement en changeant les paramètres d’appels.
La version précédente de la fonction fact n’est pas tail-recursion car même si elle s’appèle elle même (fact(n-1)), elle multiplie le résultat de cet appel par n.
Si on ré-ecrit fact pour la rendre une tail-recursion, ça aurait donné:
Java:
public long fact(long n, long res) {
return n <= 1 ? res : fact(n - 1, n*res);
}
(Cette fonction doit être appelé dans un premier temps avec res=1).
Cette fonction est d’un point de vue fonctionnel strictement équivalente à la précédente version, seulement, vous l’aurez remarqué, elle s’auto-appèle sans autre opération supplémetnaire.
Elle est donc une tail-rercursion.
Essayons de dérouler son exécution:
fact(5830, 1)
=> fact(5829, 1 * 5830)
=> fact(5828, 1 * 5830 * 5829)
=> fact(5827, 1 * 5830 * 5829 * 5828)
:
:
=> fact(1, 5830!)
Ainsi, on peut sans risque avancer que le compilateur, au moement de l’appel récursif, n’a pas besoin de garder une référence à l’étant courant, comme il devait le faire avec la version précédente (à cause de la multiplication).
Ainsi, au lieu de créer un nouveau frame dans le stack, le compilateur peut utiliser le même frame original pour effectuer l’appel récursif, ce qui élimine le problème du StackOverFlow.
Seulement, la JVM, ou plus précisément le compilateur Java ne supporte pas la tail-recursion, et cette nouvelle version lancera de même un StackOverFlowError lorsque n==5830.
Par curiosité, j’ai essayé de tester cette fonction avec Scala, ce qui donne:
Scala:
def fact(n:BigInt, res: BigInt):BigInt = {
if(n<=1)
res
else
fact(n-1, res*n)
}
Notez déjà combien l’utilisation de BigInt est plus agréable et simple avec Scala: on dirait des int ordinaires !
Et à l’exécution, surprise, avec le fameux 5830, ça marche sans problème ! Et ça marche encore avec des nombres beaucoup, beaucoup plus grands (99999) ! Bon, ça marche pas vraiment, car le calcul prendrait des heures ou des jours, mais le principe est là: Scala supporte la tail-recursion sur la JVM \o/