tail recursivity - recursivite terminale

je cherche à savoir si
faire de la récursivité terminale sous Python procure (presque) les
mêmes avantages.

Je ne pense pas :

import dis
def g(n, a=0):
... if n<1:

... return a
... else:
... return g(n-1, a+1)
...

g(3)
3

dis.dis(g)
0 SET_LINENO 1

3 SET_LINENO 2
6 LOAD_FAST 0 (n)
9 LOAD_CONST 1 (1)
12 COMPARE_OP 0 (<)
15 JUMP_IF_FALSE 11 (to 29)
18 POP_TOP

19 SET_LINENO 3
22 LOAD_FAST 1 (a)
25 RETURN_VALUE
26 JUMP_FORWARD 25 (to 54)

29 POP_TOP

30 SET_LINENO 5
33 LOAD_GLOBAL 2 (g)
36 LOAD_FAST 0 (n)
39 LOAD_CONST 1 (1)
42 BINARY_SUBTRACT
43 LOAD_FAST 1 (a)
46 LOAD_CONST 1 (1)
49 BINARY_ADD
50 CALL_FUNCTION 2
53 RETURN_VALUE

54 LOAD_CONST 0 (None)
57 RETURN_VALUE

Dans le code au-dessus, g est recursive terminale.
Or on remarque dans le desassemblage l'instruction CALL_FUNCTION (en
50) suivie de RETURN_VALUE (en 53).
Il semble donc que le cadre de pile (stack frame) est conserve et que
python n'optimise pas les recursivites terminales.

PS: Je programme, c'est tout. Je ne connais pas _exactement_ pourquoi la
récursivité terminale permet ceci ou cela. Cela viendra un jour,
peut-etre, mais pour l'instant j'apprends :-)

C'est simple, lors d'un appel de fonction, on empile un cadre de pile
(avec arguments et variables locales) qui est depile au retour de la
fonction. Si tu fais une grosse recursion, la pile contient donc tous
les cadres de tous les appels en cours et peut donc deborder.
Le but de la recursivite terminale est simplement de remplacer le cadre
actuel d'appel de fonction par celui de la fonction appelee lorsque
c'est possible (ce qui est le cas lorsque c'est la meme fonction et que
tu ne fais pas d'operation a son retour : "return g(..., ...)").

A noter qu'en general, il est facile de reecrire une recursion
terminale en iteratif donc ce n'est peut-etre pas un gros probleme.

Jean-Côme Charpentier wrote:

function factorielle(n: integer) return integer
if n = 0
return 1;
else
return n*factorielle(n-1);
end if
end factorielle

serait bien meilleur.

Non, non. C'est pareil, l'appel récursif n'est pas terminal.
Pour faire une multiplication, on commence par evaluer les deux termes à
multiplier et ensuite seulement on procède au calcul. Donc le fait que
la dernière instruction soit:
return n*factorielle(n-1)
ou return factorielle(n-1)*n ne change rien, il reste toujours
la multiplication à faire.

Un version récursive terminale de la fonction factorielle (je ne connais
pas du tout python, je risque une erreur de syntaxe):

function factorielle_aux (acc: integer, n: interger) return integer
if n = 0
return acc;
else
return factorielle_aux (n*acc, n-1);
end if
end factorielle_aux

function factorielle (n : integer) return integer
return facotirelle_aux (1, n);
end factorielle

Comme souvent pour rendre une fonction terminale récursive il faut
rajouter un paramètre.

--
Marc.

Bonjour,

L'idée de la récursivité en programmation est que le calcul est empilé
empilé empilé etc. sachant qu'on peut soit calculer avec ce que l'on a
déjà calculé (top-down) ou en "rattrappant" les résultats quand ils
finissent (bottom up ou backtrack).
Seulement si à chaque étape tu ne finis pas le calcul ça empile des
résultats partiels et ça prend vite beaucoup de mémoire, comme dans le
cas de la version naïve de Fibonacci vu qu'elle est exponentielle. Donc
il faut faire en sorte qu'à un appel récursif il n'y ait plus rien à
calculer.

Ensuite le principe est le même pour tous les langages. Seulement avec
Ocaml ça fonctionne très bien car la pile est très bien implémentée.

Pour des exemples de programmes récursifs il ya les classiques Tours de
Hanoï, fibonacci, factorielle (très facile). En Caml on fait beaucoup
d'itérations (ça vient du lambda-calcul), notament sur les listes. Donc
retournement de liste, somme des éléments, taille d'une liste. Après si
on veut s'ammuser on passe aux arbres. Etc. C'est très ammusant.

Pour la petite histoire la version "intelligente" de calcul de Fibonacci
(qui n'est pas la plus rapide actuellement) utilise l'idée du
prédécesseur en lambda-calcul découverte par Kleene. Selon ce qu'il
raconte dans un bouquin un jour il était chez le dentiste. Et comme il
avait peur de la roulette il s'est fait endormir. Quand il est revenu
chez lui il était dans le coltar. Il griffone un truc sur un bout de
papier et s'effondre sur son lit. A son réveil il remarque par hasard le
bout de papier qu'il avait complètement oublié et miracle ! Il y avait
écrit dessus le lambda-terme du prédécesseur qu'il cherchait depuis des
mois.
L'idée est de coder le résultat avec des couples pour "mémoriser" le
coup d'avant et le résultat courant. Cette technique s'adapte
parfaitement à Fibonacci vu qu'il suffit de mémoriser la valeur pour n -
1 afin de ne pas la calculer deux fois.
On peut retrouver le calcul de fibonnacci grâce à une méthode simple. En
effet la fonction de Fibonacci vient du comptage de lapins. Simplifions.
- un vieux lapin donne un jeune lapin et un vieux lapin
- un jeune lapin donne un vieux lapin.
On peut faire un système de réécriture avec ça. Notons vieux par x et
jeune par o.
=> x -> x o
=> o -> x

Donc x -> x o -> x o x -> x o x x o -> x o x x o x o x -> x o x x o x o
x x o x x o -> etc.
Dans un couple on note le combre de x et le nombre de y, ça donne
(1, 0) -> (1, 1) -> (2, 1) -> (3, 2) -> (5, 3) -> (8, 5) -> etc.

Si on regarde le premier nombre du couple on a les nombres de fibonacci.
Or pour calculer la transition "numériquement" c'est facile. Il suffit
de regarder d'où viennent les x et d'où viennent les o. On a un x quand
on avait un x ou quand on avait un o. Pour les o on en avait un que si
on avait un x. Donc f(a, b) = (a+b, a)

La technique de récursivité terminale vient de cette idée : garder le
résultat dans un accumulateur qu'on passe en argument de la fonction.
Tout simplement. Ca permet de faire en sorte que la calcul en cours soit
terminé, et donc il n'y a qu'à calculer l'étape de récurrence.. C'est un
opérateur de point fixe quoi.

Tom

R12y wrote:

[ Attention: Xpost + follow-up ]

Bonjour,

A la Fac, on nous enseigne des langages, mais pas Python.
Sur certains de ces langages (Ocaml, mais c'est pas pour troller)

Je ne vois pas où est le troll. J'adore Ocaml, il y en a qui
détestent (souvent parce qu'ils ne comprennent pas la logique de ce
genre de langage) et cela ne me perturbe pas outre mesure. Je me dis
seulement qu'ils ont loupé quelque chose et que c'est un peu dommage
mais que j'ai dû loupé moins même encore plus de chose (et que c'est
dommage aussi).

faire un
truc "récursif terminal" permet de faire de la récursivité "très
profonde", en repoussant les limites du stack overflow.

J'aime bien ce "truc", moi. La récursivité ça m'a impressionné :-).

C'est une notion assez fondamentale en programmation (Ocaml ou pas
Ocaml).

Le problème:
Au niveau professionel, OCaml n'est pas très implanté, et d'ailleurs je
suis plutot dans une boite où c'est Python qui règne en maître. Ce
n'est pas un mal, mais je recherche des exemples à difficulté
progressive de cas de recursivité terminale, et je cherche à savoir si
faire de la récursivité terminale sous Python procure (presque) les
mêmes avantages.

Auriez-vous des pistes?

PS: Je programme, c'est tout. Je ne connais pas _exactement_ pourquoi la
récursivité terminale permet ceci ou cela. Cela viendra un jour,
peut-etre, mais pour l'instant j'apprends :-)

Même lorsqu'"on programme, c'est tout", il peut être intéressant de
savoir ce qu'est la récursivité terminale et en quoi elle est
intéressante, cela permet de faire la différence entre programmer un
machin qui va rapidement planter s'il y a beaucoup d'appel et un autre
qui ne plantera pas.
Bon, comme son nom l'indique, la récusivité terminale est une
technique qui consiste à placer l'appel récursif après tous les autres
traitement d'un sous-programme. L'avantage (immense), c'est qu'un
compilateur ou un interpréteur bien fait doit voir que l'appel récursif
n'en ait pas vraiment un puisque le retour d'appel se fera sur... du
vide. Autant ne pas empiler tout ce qu'il faut pour permettre un retour
récursif et dire qu'il n'y a pas de récursivité du tout !
De la sorte, on ne repousse pas les limites du stack overflow, on le
supprime complètement : il pourra y avoir dix milliard d'appels, mis à
part le temps d'excéution, il n'y aura aucun ennui. En fait, le
compilateur ou l'intépréteur dérécursifie la chose pour la transformer
grosso-modo en boucle while.
Conclusion, si on peut transformer un programme récursif en programme
récursif terminal, on saute dessus ! Il me semble (au secours les
spécialistes), qu'il y a un théorème qui dit que l'on peut dérécursifier
n'importe quoi (mais que ce n'est pas de la tarte). En recanche,
dérécursifié un programme avec juste un appel récursif terminal est
quasi trivial.
J'aime bien Ocaml mais j'aime bien Python également (vous voyez, on
n'est pas forcément sectaire :-) ). Vu la puissance de la bête, je serai
étonné qu'elle ne fasse pas de dérécursifiction automatique. Du point de
vue de l'utilisateur, c'est simple, il faut qu'il fasse en sorte de
placer son appel récursif en fin de sous-programme. Exemple très bête
pour comprendre, d'ailleurs tellement bête que Python s'en sort
peut-être bien quand même : c'est juste pédagogique :-)

function factorielle(n: integer) return integer
if n = 0
return 1;
else
return factorielle(n-1)*n;
end if
end factorielle

serait éventuellement (très) mauvais alors que

function factorielle(n: integer) return integer
if n = 0
return 1;
else
return n*factorielle(n-1);
end if
end factorielle

serait bien meilleur.

Bon, même si je suis assez certain de l'idée générale, il est tout à
fait possible que ma réponse soit émaillée de diverses approximations,
voire de fautes grossières. Des plus spécialistes corrigeront.

Jean-Côme Charpentier

et je cherche à savoir si
faire de la récursivité terminale sous Python procure (presque) les
mêmes avantages.

Cette facilité d'optimisation ne vient pas du langage, mais de son
compilateur. Il se pourrait que ça marche ou pas avec certaines versions
de python (tout comme on pourrait envisager un compilateur OCaml qui ne
profite pas de cette opportunité). En pratique, je ne sais pas si les
interprèteurs Pythons classiques implémentent où non cette optimisation.
Pourquoi ne pas faire un test ?

Auriez-vous des pistes?

PS: Je programme, c'est tout. Je ne connais pas _exactement_ pourquoi la
récursivité terminale permet ceci ou cela. Cela viendra un jour,
peut-etre, mais pour l'instant j'apprends :-)

L'idée est à ma connaissance qu'il est assez trivial pour un compilateur
de transformer une fonction à récursivité terminale en une simple boucle
itérative, alors que c'est moins simple pour la récursivité dans son
acception la plus générale.

--
Loïc

[ Attention: Xpost + follow-up ]

Bonjour,

A la Fac, on nous enseigne des langages, mais pas Python.
Sur certains de ces langages (Ocaml, mais c'est pas pour troller) faire un
truc "récursif terminal" permet de faire de la récursivité "très
profonde", en repoussant les limites du stack overflow.

En fait, il s'agit d'une optimisation qu'effectuent certains
compilateurs/interpréteurs (dans certains langages...) en transformant
un appel recursif en itération, ce qui évite d'entasser les frames
d'appels de fonction. Il faut bien sûr que la façon dont est codée la
fonction le permette.

J'aime bien ce "truc", moi. La récursivité ça m'a impressionné :-).

C'est un autre problème. On peut utiliser des algos récursifs (et on le
fait) qu'il y ait optimisation ou pas. Mais il est clair que dans le
second cas, il faut être plus vigilant...

Le problème:
Au niveau professionel, OCaml n'est pas très implanté, et d'ailleurs je
suis plutot dans une boite où c'est Python qui règne en maître.

C'est assez rare.

Ce
n'est pas un mal, mais je recherche des exemples à difficulté
progressive de cas de recursivité terminale, et je cherche à savoir si
faire de la récursivité terminale sous Python procure (presque) les
mêmes avantages.

Non. Le compilateur et l'interpréteur CPython n'effectuent aucune
optimisation de ce type. Mais ça n'empêche pas d'utiliser la
récursivité, et c'est même une pratique assez courante.

Auriez-vous des pistes?

Des exemples d'utilisation de la récursivité ? D'une manière générale,
tout code ayant à gérer une structure arborescente tend à se baser sur
des appels récursifs. Et des structures arborescentes, on en voit pas
mal, à commencer par le système de fichiers.

PS: Je programme, c'est tout. Je ne connais pas _exactement_ pourquoi la
récursivité terminale permet ceci ou cela. Cela viendra un jour,
peut-etre, mais pour l'instant j'apprends :-)

Un version récursive terminale de la fonction factorielle (je ne connais
pas du tout python, je risque une erreur de syntaxe):

Ce qu'a écris Jean-Côme n'étant pas du Python, n'ait aucune crainte à ce
sujet !-)

function factorielle_aux (acc: integer, n: interger) return integer
if n = 0
return acc;
else
return factorielle_aux (n*acc, n-1);
end if
end factorielle_aux

function factorielle (n : integer) return integer
return facotirelle_aux (1, n);
end factorielle

Traduction Python
def factorielle(n):
def factorielle_aux(accu, n):
if n == 0:
return accu
else:
return factorielle_aux(n * accu, n - 1)
return factorielle_aux(1, n)

Comme souvent pour rendre une fonction terminale récursive il faut
rajouter un paramètre.

... qui sert à "accumuler" les résultats des appels précédents, d'où son
appelation dans la plupart des exemples...

On Mon, 29 Aug 2005 23:06:20 +0200, Bruno Desthuilliers wrote:

Auriez-vous des pistes?
Des exemples d'utilisation de la récursivité ?

En fait, c'est pas ça, mais dans un fil de ce groupe j'avais posté un
truc sur la suppression des commentaires dans un fichier texte.
Pour le fun, mais vraiment pour le fun, j'avais fait ça en fonctionnel et
recursif.
Sur 5 ou 10 lignes le test est passé (la machine à 1Go de RAM et un peu
plus en swap). Sur un fichier réel (celui sample de awstats de quelques
centaines de lignes) j'ai dépassé la profondeur de récursion
autorisée. Le fichier en lui même est relativement léger par rapport à
la RAM disponible. J'y vois un problème.

L'agorithme a été simplement de stocker tout le fichier dans une liste,
puis ensuite de travailler (recursivement) sur cette liste en générant
une liste des lignes qui ne sont pas des commentaires.

D'ailleurs je balance le code qui l'a fait:

################################################
import sys, string, os

fichierEntree=open(sys.argv[1],"r")
nomFichier=(os.getcwd() + "/tmp.txt")

fichierSortie=open(nomFichier,"w")
linesList=fichierEntree.readlines()


def cleanList (inputList,outputList=[]):
try:
if (inputList[0][0]=='#') or (inputList[0][0]=='n'):
cleanList(inputList[1:],outputList)
else:
line=inputList[0]
outputList= outputList + line
cleanList(inputList[1:], outputList)
except IndexError:
return outputList


def listToFile (aList,outputFileName):
opf=open(outputFileName)
try:
opf.writelines(aList[0])
listToFile(aList[1:])
except IndexError:
opf.writelines('n')
opf.close()

def cleanFile (fileName):

# os.rename("tmp.txt", sys.argv[1])
########################################################

Bon j'avoue que c'est énormément de lignes pour presque rien, mais
j'essayais de faire de la "recursivité terminale" (Ai-je réussi?
Normalement oui)... alors forcément, le code se voit rajouter des
/plugins/ ça et là...

--
SPIP, phpNuke, Plone, opengroupware... c'est bien
CPS c'est mieux: http://www.cps-project.org/
Hébergement de sites CPS: http://www.objectis.org/

R12y <mihamina.rakotomandimby@etu.univ-orleans.fr> writes:

A la Fac, on nous enseigne des langages, mais pas Python.
Sur certains de ces langages (Ocaml, mais c'est pas pour troller) faire un
truc "récursif terminal" permet de faire de la récursivité "très
profonde", en repoussant les limites du stack overflow.

J'aime bien ce "truc", moi. La récursivité ça m'a impressionné :-).

Le problème:
Au niveau professionel, OCaml n'est pas très implanté, et d'ailleurs je
suis plutot dans une boite où c'est Python qui règne en maître. Ce
n'est pas un mal, mais je recherche des exemples à difficulté
progressive de cas de recursivité terminale, et je cherche à savoir si
faire de la récursivité terminale sous Python procure (presque) les
mêmes avantages.

Certaines entreprises malines tirent profit d'OCaml (ou de Lisp ou
d'autres langages avancés).
Par exemple en Angleterre: http://www.ffconsultancy.com/

La récursivité terminale est triviale, car on peut facilement et
automatiquement la transformer en itération.

La question sera s'il est plus clair d'écrire une boucle sous forme
itérative ou sous forme récursive terminale?

Voici le même algorithme exprimé sous forme recursive terminale, sous
forme itérative "structurée", sous forme itérative "assembleur".
Laquelle est la plus claire?

(defun fact (n)
(labels ((loop (n r)
(if (<= n 1)
r
(loop (- n 1) (* n r)))))
(loop n 1)))

(defun fact (n)
(let ((r 1))
(loop while (< 1 n)
do (setf n (- n 1)
r (* n r)))
r))

(defun fact (n)
(let ((r 1))
(tagbody
:loop
(if (< n 1) (go :done))
(setf n (- n 1)
r (* n r))
(go :loop)
:done)
r))

Le fait que la forme récursive terminale évite la modification de
variables (assigment, setf), fait que cette forme a de bonnes
propriétés pour être utilisable dans un langage purement fonctionnel.
Par exemple, dans le langage mathématique, où les variables ne
changement pas de valeur (ce qu'on appelle "variable" en programmation
procédurale, ce sont en fait des suites mathématiques, pas des
variables mathématique).

On a donc une correspondance plus directe entre une forme récursive
terminale et une définition algorithmique récursive. (Il suffit de
compter dans la litérature mathématique-algorithmique, combien de fois
un algorithme donné est décrit sous une forme itérative ou sous une
forme récursive; en général, c'est une forme récursive:
fact(n):{n!=n*(n-1)!; 1!=1}
gcd(p,q):{(p=q)-->p; (p<q)-->gcd(q-p,p); (p>q)-->gcd(p-q,q)}
etc.

Maintenant, comme il y a des langages qui ne spécifient pas la
dérécursivation terminale automatique, et comme il y a des algorithmes
récursifs non-terminaux, un programmeur doit savoir dérécursiver
manuellement de toutes façons. (C'est trivial si on utilise une pile
explicite).

--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay

On Mon, 29 Aug 2005 23:06:20 +0200, Bruno Desthuilliers wrote:

Auriez-vous des pistes?

Des exemples d'utilisation de la récursivité ?

En fait, c'est pas ça, mais dans un fil de ce groupe j'avais posté un
truc sur la suppression des commentaires dans un fichier texte.
Pour le fun, mais vraiment pour le fun, j'avais fait ça en fonctionnel et
recursif.

Même s'il supporte un certain nombre de constructions venant de la
programmation fonctionnelle (dont le pré-requis: les fonctions sont des
objets comme les autres), Python n'est pas très adapté à ce genre de
construction, justement du fait qu'il n'optimise pas la récursivité
terminale.

Sur 5 ou 10 lignes le test est passé (la machine à 1Go de RAM et un peu
plus en swap). Sur un fichier réel (celui sample de awstats de quelques
centaines de lignes) j'ai dépassé la profondeur de récursion
autorisée. Le fichier en lui même est relativement léger par rapport à
la RAM disponible. J'y vois un problème.

Ah bon ?-)

L'agorithme a été simplement de stocker tout le fichier dans une liste,

C'est déjà un problème si ton programme - qu'il utilise ou non la
récursivité - doit gérer des fichiers de taille arbitraire. Il vaut
mieux dans ce cas, et autant que possible, travailler ligne à ligne, ou
avec des 'blocs' de lignes minimums contenant le contexte nécesaire au
traitement (ie : le programme lit une première ligne, essaie de la
traiter, et s'il n'y a pas assez de contexte lis les lignes suivantes
jusqu'à avoir le contexte nécessaire).

puis ensuite de travailler (recursivement) sur cette liste en générant
une liste des lignes qui ne sont pas des commentaires.

D'ailleurs je balance le code qui l'a fait:

################################################
import sys, string, os

fichierEntree=open(sys.argv[1],"r")
nomFichier=(os.getcwd() + "/tmp.txt")

fichierSortie=open(nomFichier,"w")
linesList=fichierEntree.readlines()


def cleanList (inputList,outputList=[]):

Attention aux valeurs par défaut, c'est un gotcha classique en Python.

try:
if (inputList[0][0]=='#') or (inputList[0][0]=='n'):
Et si le commentaire n'est pas au début de la ligne ?-)

cleanList(inputList[1:],outputList)

Tu utilises les effets de bord au lieu de retourner un résultat... pas
du tout fonctionnel, ça.

else:
line=inputList[0]
outputList= outputList + line

Est-ce que list.extend(otherList) ne serait pas plus efficace ici ?
Vérifie au niveau du byte-code généré, mais il me semble que cette
construction alloue une nouvelle liste à chaque fois (un gourou dans les
parages ?).

Accessoirement, je ne vois pas l'intérêt de la variable intermédiaire
'line'...

cleanList(inputList[1:], outputList)
except IndexError:
return outputList


def listToFile (aList,outputFileName):
opf=open(outputFileName)
try:
opf.writelines(aList[0])
listToFile(aList[1:])

Il manque un argument à ton appel, non ?

Par ailleurs, là, il n'y a *aucune* justification à l'emploi de la
récursivité. En plus, tu ouvres sans arrêt le même fichier, et tu oublie
de le fermer. Au moins, passe un objet fichier, pas le nom du fichier,
et laisse au code appelant le soin de fournir le fichier ouvert
(bénéfice secondaire: tu peux passer n'importe quel objet 'file-like' -
par exemple sys.stdout, ou un cStringIO).

except IndexError:
opf.writelines('n')
opf.close()

(snip)

Bon j'avoue que c'est énormément de lignes pour presque rien,

Pas seulement pour rien.

Tu a le même comportement - problèmes de perfs et de mémoire en moins,
flexibilité en plus - avec le code suivant:

def clean(input, output, filter_func):
output.writelines(line for line in input
if filter_func(line.strip()))
def main(argv):
input = ...
output = ...
clean(input,
output,
lamba line: bool(line) and not line.startswith('#'))

if __name__ == '__main__':
import sys
sys.exit(main(sys.argv))

mais
j'essayais de faire de la "recursivité terminale" (Ai-je réussi?
Normalement oui)...

Forcément non, puisque Python n'optimise pas la récursivité terminale.
Et non par ailleurs, puisque comme son nom l'indique, il y a recursion
terminale quand l'appel récursif est la dernière expression de la
fonction, et qu'elle n'implique aucun autre traitement que cet appel.

Une version 'tail-recursive' de ton algo serait:

def clean_lines(lines, filter_func):
def clean_rec(accu, lines, filter_func):
if not lines:
return accu
else:
line, lines = lines[0], lines[1:]
if filter_func(line):
accu.append(line)
return clean_rec(accu, lines, filter_func)

return clean_rec([], lines, filter_func)

(NB : pas testé)

mais bon, ça n'évite pas de faire de multiples sous-copies de la liste...

Bref, en Python, utilise la récursivité là où elle a un sens
(arborescences par exemple...), et préfère les itérateurs/générateurs
(évaluation paresseuse) pour les traitements sur des listes de taille
arbitraire.

Pour ce qui est de jouer avec la récursion terminale, Common Lisp,
Scheme, Caml ou Haskell (à vérifier) sont certainement plus appropriés !-)