Récursivité

🌱 Qu’est-ce que la récursivité ?

La récursivité est un concept fondamental en informatique où une fonction s'appelle elle-même pour résoudre un problème.

On parle de fonction récursive.

C’est comme si la fonction disait :

"Je vais résoudre ce problème... en demandant à une version plus simple de moi-même de le résoudre !"

⚠️ Une fonction récursive doit toujours avoir une condition d'arrêt (appelée cas de base) pour éviter de tourner à l’infini.

🔁 Schéma type d’une fonction récursive

def fonction_recursive(param):
    if condition_arret(param):       # Cas de base
        return valeur_simple
    else:                             # Cas récursif
        return fonction_recursive(nouveau_param)

📌 Exemple 1 : Factorielle

La factorielle d’un nombre entier positif n se note n! et vaut :

$n!=n×(n−1)×(n−2)×...×1$

Par exemple, 5! = 5 × 4 × 3 × 2 × 1 = 120

Version récursive

def factorielle(n):
    if n == 0 or n == 1:     # Cas de base
        return 1
    else:
        return n * factorielle(n - 1)  # Cas récursif

Appel :

print(factorielle(5))  # Affiche 120

📌 Exemple 2 : Somme des entiers jusqu’à n

$somme(n)=n+(n−1)+...+1$

Version récursive

def somme(n):
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)

📌 Exemple 3 : Suite de Fibonacci

Définie par :

$F(0)=0,F(1)=1$

$F(n)=F(n−1)+F(n−2)pour n≥2$

Version récursive :

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

🔥 Attention : coût élevé !

Cet algorithme est simple, mais très lent pour des grandes valeurs de n :

• Beaucoup d'appels sont répétés inutilement.

• Par exemple, fibonacci(5) appelle fibonacci(4) deux fois, etc.

👉 On peut optimiser cela avec la mémoïsation (on verra plus bas).

📊 Comparaison : Récursif vs Itératif

➕ Avantages du récursif

➖ Inconvénients

📐 Fonctionnement technique : la pile d’appels

Chaque fois qu’une fonction s’appelle elle-même, une nouvelle instance est empilée dans la mémoire. On appelle cela la pile d’appels (call stack).

🧱 Quand une fonction atteint le cas de base, les appels sont dépilés dans l’ordre inverse.

C’est comme une pile d’assiettes :

• On empile jusqu’à arriver au cas de base

• Puis on dépile en résolvant chaque niveau

🚫 Limite de récursivité

Python fixe une limite maximale de récursion (environ 1000 appels par défaut).

import sys
print(sys.getrecursionlimit())  # Affiche 1000

Pour aller plus loin :

sys.setrecursionlimit(2000)  # augmente la limite

⚠️ À utiliser avec précaution : si la pile devient trop grande → crash du programme.

✅ Récursion terminale

Une récursion terminale est une récursion où l’appel récursif est la dernière instruction exécutée dans la fonction.

Exemple :

def compte(n):
    if n == 0:
        return
    print(n)
    return compte(n - 1)

👉 En théorie, les langages optimisent ce cas pour éviter la pile, mais Python ne le fait pas.

🧠 Optimisation : mémoïsation

Lorsqu’une fonction récursive est appelée plusieurs fois avec les mêmes arguments, on peut mémoriser les résultats pour éviter les recalculs.

Exemple optimisé de Fibonacci :

memo = {}

def fibonacci(n):
    if n in memo:
        return memo[n]
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fibonacci(n - 1) + fibonacci(n - 2)
    memo[n] = result
    return result

👉 Beaucoup plus rapide !

🌲 La récursivité structurelle : les arbres et les graphes

La récursivité est très utile pour parcourir des structures comme les arbres (ex : arbre binaire, système de fichiers, etc.).

Exemple : affichage d’un arbre

def afficher_arbre(arbre):
    if arbre is None:
        return
    print(arbre['valeur'])
    afficher_arbre(arbre['gauche'])
    afficher_arbre(arbre['droite'])

🔍 À retenir