Chapitre 3: Fonctions récursives

Définition et exemple

Fonction récursive

Une fonction récursive est une fonction qui s'appelle elle-même dans sa définition.

Commençons par un exemple pour clarifier un peu les choses.

Vous voulez demander à un utilisateur une entrée par exemple son âge, et vous voulez vous assurer que l'utilisateur vous donne bien une valeur entière positive.

On peut implémenter cela avec une boucle while.

age = None
while not(age):
    age = int(input("Quel âge avez-vous?"))
    if age > 0:
        print("Merci pour votre réponse)
    # on affecte None à age pour relancer un tour de boucle
    print("L'age doit être un entier positif")
    age = None
        

Mais il est aussi tout à fait possible d'utiliser une fonction récursive comme ceci:

def quel_age():
    age = int(input("Quel âge avez-vous?"))
    if age > 0:
        return age
    # L'age n'est pas positif, il faut recommencer
    print("L'age doit être un entier positif")
    # on fait l'appel récursif pour reposer la question
    quel_age()

age = quel_age() # appel de la fonction et assignation de la valeur retournée à la variable age

Comme vous le voyez cette fonction continuera de s'appeler tant que nécessaire. On a donc bien remplacé la boucle avec cette fonction.

Comment définir une fonction récursive?

Pour écrire une fonction récursive il faut:

• Traiter attentivement le cas récursif du passage des valeurs renvoyées par l'appel précédent à l'appel suivant.

• Prévoir le cas de base qui ne nécessite pas de rappel de la fonction afin d'arrêter la boucle.

def puissance2(n: int) -> int:
    puissance = 1
    for i in range(n):
        puissance = puissance * 2
    return puissance

>>> puissance2(8)
256

def puissance_recursive(exposant):
    # cas de base
    if exposant == 0:
        return 1
    # appel recursif
    return 2 * puissance_recursive(exposant - 1 )

puissance_3 = puissance_recursive(3)

Pile d'exécution

Bien que la gestion de la mémoire soit «cachée» au programmeur en Python, qu'il existe deux façons d'allouer de la mémoire à un programme lors de son exécution (on parle d'allocation dynamique).

• Le tas (heap en anglais) est un segment de mémoire que l'on peut faire grandir ou rétrécir à la demande.
• L'autre segment de mémoire utilisé est la pile d'exécution (call stack). La pile sert à enregistrer des informations au sujet des fonctions actives dans un programme informatique, c'est celle qui nous intéresse ici.

Étant donné que la pile d'exécution est une pile, l'appelant pousse l'adresse de retour sur la pile, et la fonction appelée, quand elle se termine, récupère l'adresse de retour au sommet de la pile d'exécution (et y transfère le contrôle). Si une fonction appelée appelle une autre fonction, elle poussera son adresse de retour sur la pile d'exécution. Les adresses de retour s'accumulent donc sur la pile d'exécution et sont récupérées une à une lors de la fin de l'exécution des fonctions. Si l'accumulation des adresses de retour consomme tout l'espace alloué à la pile d'exécution, un message d'erreur appelé un dépassement de pile se produit.

[Article Wikipédia sur la pile d'exécution]{.cite-source}

Pour bien comprendre comment fonctionne la pile d'exécution, on peut exécuter la fonction puissance_recursive pas à pas sur pythontutor.

Sur cette animation la pile est «à l'envers»!

Efficacité des algorithmes récursifs

L'écriture d'algorithmes récursifs peut-être très élégante et concise, cependant elle peut avoir des conséquences très néfastes sur leur efficacité. La taille de la pile peut croitre au-dessus des limites de la mémoire, ou encore certains calculs identiques peuvent être réalisés plusieurs fois.

Nous allons voir comment l'utilisation d'un accumulateur peut permettre de passer des valeurs d'un appel à un autre lors de la récursion.

def puissance_rec_acc(exposant, acc=1):
    # cas de base
    if exposant == 0:
        return acc
    # appel recursif
    return puissance_rec_acc(exposant - 1, 2*acc )
puissance_rec_acc(4)

L'utilisation d'un accumulateur est parfois indispensable comme dans les exercices 5 et 6, voire indispensable comme dans le calcul des termes de Fibonacci de grand ordre(exercice 7).