Aller au contenu

Fonctions récursives

Définition

Une fonction est dite récursive si elle contient un appel à elle-même dans sa propre définition. (Implicitement aussi, si c'est via une autre fonction.)

Quelles conséquences ?

Devinez ce que font les scripts suivants, ils contiennent des fonctions récursives :

🐍 Script Python
def f_1():
    print("Bonjour")
    f_1()

f_1()
Réponse

Ce script affiche Bonjour de nombreuses fois.

⚠ En théorie jusqu'à l'infini, mais Python arrête l'exécution au bout d'un moment et affiche un message d'erreur. Nous expliquerons pourquoi plus tard.

🐍 Script Python
def f_2():
    f_2()
    print("Bonjour")

f_2()
Réponse

Ce script n'affiche jamais Bonjour, mais...

⚠ Il y a de nombreux appels récursifs, (en théorie infiniment, mais...) jusqu'au message d'erreur de Python.

🐍 Script Python
def f_3():
    if False:
        f_3()
    print("Bonjour")

f_3()
Réponse

Ce script affiche Bonjour une seule fois, puis termine. Cette fonction est récursive (par définition), mais, concrètement, il n'y a aucun appel récursif, par construction.

🐍 Script Python
def f_4(n):
    print(n)
    if n > 0:
        f_4(n - 1)

f_4(4)
Réponse

Ce script affiche

📤 Sortie
4
3
2
1
0

XKCD 1557 1

  1. XKCD 1557 : Ozymandias ↩