Donc, vulgarisons un peu. Ca sera un article bien prise de tête. Lisez-le un dimanche soir quand vous ne captez pas arte (et si vous ne pigez rien, c’est pas grave, revenez dans un an, moi je le fais bien avec tous les articles d’Alex Martelli).

Un appel récursif, c’est une fonction qui s’appelle elle-même. Et en Python ça donne ça:

def fonction_recursive():

    print "Je suis récursive, fuck yeah !"

    fonction_recursive()

Et sa sortie va ressembler à ça:

>>> fonction_recursive()
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
Je suis récursive, fuck yeah !
[...]

Un peu comme une boucle infinie:

while True:
    print "Je suis récursive, fuck yeah !"

Car la fonction s’appelle elle même indéfiniement.

Les boucles infinies peuvent être utiles, mais en Python, les récursions infinies sont vachement craignos, parcequ’elles aboutissent toujours à ce message d’erreur:

RuntimeError: maximum recursion depth exceeded

En effet, une boucle infinie est une sucession d’opération les une après les autres, mais une récursion infinie est une succession d’opérations les unes dans les autres. Et comme Python garde en mémoire une pile de chaque appel de fonction (c’est entre autre ce qui vous permet de voir le fameux stack trace quand il y a une erreur et remonter jusqu’à la source du plantage au moment d’une exception), il finit par remplir la pile, qui par défaut a une limite de 1000 entrées.

Du coup, en Python, quand on fait du récursif, on est obligé de faire une condition de sortie, du genre:

def fonction_recursive(count=0):

    if count > 100:
        return 

    print "Je suis récursive, fuck yeah !"

    fonction_recursive(count + 1)

Ce qui va ici limité le nombre d’appels récursifs à 100.

On ne va pas discuter de la pertinence de la récursivité, mais toujours est-il que Python est limité de ce côté, et c’est un choix délibéré.

Il est limité car dans d’autres langages, tels que Lisp et Erlang, on peut faire autant de récursion qu’on le souhaite, pourvu qu’on écrive la récursion d’une certaine façon. C’est ce qu’on appelle la TCO, Tail Call Optimisation: le pile d’appels est vidée au fur et à mesure et ne devient jamais pleine.

Comment ça s’utilise et pourquoi ça marche peut faire l’objet d’un article à lui tout seul, et ce n’est pas le but ici.

Le but de l’article est de répondre à une question que certains habitués de la récursion se posent: comment faire des state machines en Python ?

En effet, une manière très élégante de coder une state machine, ou automate fini, est justement d’utiliser une récusion infinie:

def etat3(a, b, c):

    print "Etat 3"
    print a, b, c

    etat1(a, b, c)

def etat2(a, b, c):

    print "Etat 2"
    print a, b, c

    etat3(a, b, c)

def etat1(a, b, c):

    print "Etat 1"
    print a, b, c

    etat2(a, b, c)

etat1(1, 2, 3)

Cela permet de faire transiter le code d’un état à un autre sans se soucier de stocker l’état courant, sans barder le programme de if/else, et le code est beaucoup plus élégant et simple à suivre (c’est un état qui change, c’est tout):

etat1 => etat2 => etat3 => etat1 => etat2 => etat3 => etc

Enfin plus simple, pourvu qu’on code proprement, car la récursion infinie, c’est au fond une forme ultime de goto (instruction qui par ailleurs est bannie de Python).

Mais, si vous l’avez remarqué, pour faire une state machine de cette manière, il nous faut des appels infinis (la state machine n’est pas sensée s’arrêter au bout de 1000 appels), et donc une TCO, ce que Python ne possède pas.

C’est évidement sans comptez notre Guido favoris qui nous a pondu la solution au problème, version Python:

def etat3(a, b, c):

    print "Etat 3"
    print a, b, c

    return etat1, [a, b, c]

def etat2(a, b, c):

    print "Etat 2"
    print a, b, c

    return etat3, [a, b, c]

def etat1(a, b, c):

    print "Etat 1"
    print a, b, c

    return etat2, [a, b, c]

func, args = etat1, [1, 2, 3]
while True:
  func, args = func(*args)

Et voilà, nous avons le même effet (et les mêmes possibilités de sortie, condition, etc), mais en procédural plutôt qu’en purement fonctionnel. Toute l’astuce consiste à retourner le prochain état désiré au lieu de l’éxécuter, et de laisser la boucle principale se charger des appels.

Le bloc while est rarement utilisé en Python, à part justement pour des main loops (souvent infinies), et c’est probablement l’usage le plus pertinent que j’ai vu depuis longtemps.