Discussion :

[jack-ft]

oui, c'est ce que font certains compilateurs d'ailleurs, ils "transforment" ou "considèrent" les fonctions récursives terminales comme des itérations (c'est le cas du compilateur Scheme par exemple: "Ce que dit très précisément la norme de Scheme, c'est qu'une récursivité terminale sera traitée comme une itération, donc sans pile.")

Oui, c'est ce que faisait déjà le compilateur Le_Lisp (dans les années 70-80). Comme le pseudo-assembleur virtuel LLM3 généré était "facile" à lire, on pouvait vérifier que le compilateur utilisait un "goto" (sans pile) et non un "gosub" (avec empilement du contexte).

Attention toutefois à certains pièges. J'ai dit:

Lorsqu'il n'y en a qu'une (comme pour la factorielle), l'algo peut la plupart du temps être transformé en récusivité terminale voire en simple itération (donc pas besoin de pile).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
define factorielle (N)
if N == 0
then return 1
else return N * factorielle (N - 1)
fi

Ce code n'est pas récursif terminal, contrairement à ce qu'il pourrait sembler à première vue!
(voir le premier contre-exemple de http://fr.wikipedia.org/wiki/Récursion_terminale)

En effet, bien que l'appel de factorielle (N - 1) semble apparaitre en dernier dans le code, il faut d'abord calculer N et factorielle (N - 1) avant de les multiplier entre eux. Dans ce cas, le compilateur ne peut pas se passer de pile (pour empiler N et la référence de l'appel à la multiplication, puis N-1 et la référence de l'appel à la multiplication, etc.)!
Je serais surpris, voire impressionné, si un compilateur arrivait à transformer ce code en itération!
Alors qu'un bête être humain le fait sans problème en énumérant les nombres à multiplier (soit de 1 à N, soit de N à 1):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
define factorielle (N)
RESULT := 1
for I from 1 to N
do RESULT *= I
I++
done
return RESULT

D'ailleurs, dans toutes les formules données par récurrence (au sens mathématique), comme factorielle ou fibonacci, il est plus simple de calculer les valeurs dans l'ordre croissant, en mémorisant/stockant celles qui seront utiles pour le calcul de l'élément suivant.
Ainsi, il suffit de garder (dans un coin) factorielle(n) pour calculer factorielle(n+1).
Il suffit de garder (dans 2 coins) fibo(n-1) et fibo(n) pour calculer le suivant fibo(n+1). (voir algo précédemment donné)
Évidemment, dans des cas plus compliqués, comme la fonction d'Ackermann (ou d'autres fonctions à plus d'un argument), le nombre de coins peut exploser!

Ce procédé peut d'ailleurs plus ou moins être automatisé en remplaçant les fonctions par des "fonctions-mémoire", qui se souviennent de tous les éléments déjà calculés et retournent la valeur calculée et stockée plutôt que de la recalculer.

Pour la factorielle, ce n'est pas intéressant si on n'a qu'un seul calcul de factorielle à effectuer. En revanche, si on en a un 2ème, si le nombre est plus petit, le résultat est immédiatement retourné, et s'il est plus grand, seules les multiplications supplémentaires seront effectuées.

Pour fibonacci, c'est intéressant dès le premier calcul:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
define fibonacci (N)
if is_stored_fibonacci(N)
then return stored_value_fibonacci(N)
elsif N == 0
then store_fibonacci(0, 1)
    return 1
elsif N == 1
then store_fibonacci(1, 1)
    return 1
else return fibonacci (N - 1) + fibonacci (N - 2)
fi

Ce code (qui reste récursif) ne fait que 2*N additions, alors que, dans le code récursif traditionnel, le nombre d'additions est exponentiel (de l'ordre de ((sqrt(5)+1)/2)**N probablement (à vérifier...)).

[Sve@r]

D'ailleurs, dans toutes les formules données par récurrence (au sens mathématique), comme factorielle ou fibonacci, il est plus simple de calculer les valeurs dans l'ordre croissant, en mémorisant/stockant celles qui seront utiles pour le calcul de l'élément suivant.
Ainsi, il suffit de garder (dans un coin) factorielle(n) pour calculer factorielle(n+1).
Il suffit de garder (dans 2 coins) fibo(n-1) et fibo(n) pour calculer le suivant fibo(n+1). (voir algo précédemment donné)

Ce procédé peut d'ailleurs plus ou moins être automatisé en remplaçant les fonctions par des "fonctions-mémoire", qui se souviennent de tous les éléments déjà calculés et retournent la valeur calculée et stockée plutôt que de la recalculer.

Ce qui, en Python, est très facile à faire grâce aux décorateurs. Suffit de l'écrire puis on le positionne sur la fonction de son choix (qui, elle, reste inchangée dans son code)...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
def optimize(func):
	def wrapper(n):
		print "début wrapper"
		# Si le nombre n'a pas déjà été traité
		if n not in wrapper.__tab.viewkeys():
			# On le traite et on le mémorise
			wrapper.__tab[n]=func(n)
		# if
		print "fin wrapper"
 
		# Ici le nombre a été traité et son résultat mémorisé - On le renvoie
		return wrapper.__tab[n]
	# wrapper()
	wrapper.__tab={}
	return wrapper
# optimize()
 
@optimize   # Positionnement du décorateur sur la factorielle (on ne change absolument rien à son code d'origine)
def factorielle(n):
	print "inside fact", n
	if n < 2: return 1
	return n * factorielle(n-1)
# factorielle()
 
@optimize   # Positionnement du décorateur sur la fibonacci
def fibonacci(n):
	print "inside fib", n
	if n <= 2 : return 1
	return fibonacci(n-2)+fibonacci(n-1)
# fibonacci()
 
print factorielle(5)       # Ici la fonction fera tout le calcul en récursif
print factorielle(4)       # Ici son décorateur prendra le relai et renverra la valeur déjà calculée lors de 5 * fact(4)
print fibonacci(7)       # Ici la fonction fera tout le calcul en récursif (mais fera appel au décorateur à chaque fois qu'un fib(X) déjà calculé sera redemandé)
print fibonacci(4)       # Ici son décorateur prendra le relai et renverra la valeur déjà calculée lors de fibonacci(4) + fibonacci(5)

Le calcul d'un fibonacci(41) prend 27 secondes en récursif standard... et il est instantané en utilisant les décorateurs. Dommage qu'il n'y ait pas de décorateur en shell...

Alors qu'un bête être humain le fait sans problème en énumérant les nombres à multiplier (soit de 1 à N, soit de N à 1):

Oui. Mais l'humain un peu moins bête fait alors partir son énumération à 2 et non 1

[disedorgue]

Et puis il y a les cas "tordus"...
Challenge: Quelqu'un a-t-il une implémentation non récursive de la fonction d'Ackermann?

Pour ceux que cela peut intéresser, il y a le lien ci-dessous qui donne l'écriture de la fonction d'Ackermann dans un nombre impressionnant de langage et dont une version itérative en perl ainsi que d'autres versions qui utilise la "mémoïsation":
http://rosettacode.org/wiki/Ackermann_function