2. Récursivité

2.1. Extrait du programme

Notion	Savoir faire	Observations
Récursivité	Écrire un programme récursif. Analyser le fonctionnement d’un programme récursif.	Des exemples relevant de domaines variés sont à privilégier.

2.2. Définition

2.2.1. Première approche

Definition 2.1 (Fonction récursive)

Une fonction récursive est une fonction qui s’appelle elle-même

def f():
    print("Je suis une fonction récursive")
    return f()

f()

Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Je suis une fonction récursive
Unexpected exception formatting exception. Falling back to standard exception

Dans l’exemple ci-dessus, l’appel récursif ne termine pas et c’est un souci.

Avertissement

Pour éviter le cas précédent qui donne mauvaise réputation à la récursivité, on fera attention à toujours mettre une condition d’arrêt.

Ce problème est similaire au problème de la boucle while où la condition n’est jamais remplie.

Note

Acronymes récursifs On peut signaler la présence d’acronymes récursifs en informatique, comme GNU is Not Unix ou PHP Hypertext Processor, ou encore VISA.

Attention à la récursivité non terminale, par exemple dans un interpréteur type bash.

:(){ :|:& };:

Le code suivant définit une fonction nommée :. Cette fonction s’appelle elle-même sans condition d’arrêt, mais de plus, elle envoie sa sortie standard sur l’entrée standard d’une nouvelle instance d’elle même. Cette dernière instance est mis en background avec le &.

En bash, la définition d’une fonction se fait avec f(var) { echo $var } et s’appelle avec f var.

2.3. Récursivite avec cas de base

On peut consulter l’exemple suivant sur la somme des entiers naturels.