Langage et programmation

🌿 Chapitre : Récursivité

On parle de récursivité lorsqu’une fonction s’appelle elle-même. C’est une technique de programmation qui s’appuie sur les piles d’appel de fonctions :

Lorsqu’une fonction est appelée, elle est placée au sommet de la pile d’exécution.
Lorsque l’exécution d’une fonction est terminée, elle est dépilée.
Une fonction qui n’est pas au sommet de la pile a interrompu son exécution : elle reprendra lorsqu’elle se trouvera au sommet de la pile.

Il est nécessaire que les appels récursifs se terminent. Il est donc toujours nécessaire d’avoir un cas de base.

La force de cette technique de programmation est qu’elle permet de faire des retours en arrière lors de l’exécution d’un algorithme. Nous le verrons par exemple lors du parcours des arbres binaires. Notons qu’un algorithme récursif peut toujours s’écrire également de manière itérative.

Dans les cas les plus simples, un algorithme récursif s’écrit à partir de :

Un cas de base (condition d’arrêt).
Une relation de récurrence (appel récursif).

Exemple du calcul d´une factorielle :

\[ \begin{cases} \text{fact}(0) = 1 \\ \forall n \in \mathbb{N}, \ \text{fact}(n) = n \times \text{fact}(n-1) \end{cases} \]

Exemple en Python :


def fact(n):
    """
    Fonction factorielle récursive
    """
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

# Test
print(fact(5))  # 120

Quelques points clés :

La fonction doit avoir un cas de base pour éviter une récursion infinie.
Chaque appel récursif réduit le problème jusqu'au cas de base.

🔗 Cet exercice de bac 2023 illustre simplement la notion de récursivité.