La récursivité est un concept fondamental en informatique et en programmation. Elle consiste à définir une fonction en utilisant une ou plusieurs instances de cette même fonction.

En d'autres termes, une fonction récursive est une fonction qui s'appelle elle-même à l'intérieur de sa propre définition. Cela permet de résoudre des problèmes complexes en les divisant en sous-problèmes plus simples, qui sont ensuite résolus en appelant la fonction récursive sur les sous-problèmes.

Principe fondamental : Diviser pour régner

La récursivité suit le principe du "diviser pour régner" (divide and conquer) : un problème complexe est décomposé en sous-problèmes plus simples de même nature, jusqu'à obtenir des cas suffisamment simples pour être résolus directement.

Attention : Boucles infinies

Il est important de noter que la récursion peut conduire à des boucles infinies si elle n'est pas gérée correctement. Il est donc essentiel de définir une condition de sortie pour la fonction récursive, appelée condition de base (ou cas de base), qui permet de sortir de l'appel récursif et de terminer la fonction.

La récursivité est largement utilisée dans de nombreux domaines de l'informatique, notamment en mathématiques, en algorithmique et en programmation. Elle peut être utilisée pour résoudre des problèmes tels que :

La recherche de chemin dans un graphe
La génération de permutations
La recherche d'objets dans un arbre (parcours)
Les algorithmes de tri (tri rapide, tri fusion)
Les fractales et les dessins récursifs
Les problèmes mathématiques (factorielle, suite de Fibonacci)

Premiers exemples de fonctions récursives

Exemple 1 : La fonction factorielle

Définition mathématique

La fonction factorielle est définie comme suit :

$$n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$$

Avec par convention : $0! = 1$

On peut définir une fonction récursive pour calculer la factorielle de n :

def factorielle(n):
    """
    Calcule la factorielle de n de manière récursive
    
    Paramètres:
        n (int): Un entier positif ou nul
        
    Retourne:
        int: n!
    """
    # Condition de base : si n est égal à 0
    if n == 0:
        return 1
    
    # Appel récursif : n * factorielle(n-1)
    return n * factorielle(n - 1)

# Tests
print(factorielle(5))  # 120 (5*4*3*2*1)
print(factorielle(0))  # 1
print(factorielle(10)) # 3628800

Explication :

Condition de base : if n == 0: return 1 - La fonction s'arrête quand n atteint 0.
Appel récursif : return n * factorielle(n-1) - La fonction s'appelle elle-même avec un argument plus petit (n-1).

Exemple 2 : La somme des n premiers nombres

On peut définir une fonction récursive pour calculer la somme des n premiers nombres entiers :

def somme(n):
    """
    Calcule la somme des n premiers nombres entiers (1 + 2 + ... + n)
    
    Paramètres:
        n (int): Un entier positif
        
    Retourne:
        int: La somme 1+2+...+n
    """
    # Condition de base : si n est égal à 1
    if n == 1:
        return 1
    
    # Appel récursif : n + somme(n-1)
    return n + somme(n - 1)

# Tests
print(somme(5))   # 15 (5+4+3+2+1)
print(somme(10))  # 55
print(somme(100)) # 5050

Explication :

Condition de base : if n == 1: return 1 - La fonction s'arrête quand n atteint 1.
Appel récursif : return n + somme(n-1) - La fonction s'appelle elle-même avec n-1.

Visualisation de l'exécution récursive

Pour mieux comprendre comment fonctionne la récursivité, visualisons l'exécution de factorielle(4) :

Appel initial : factorielle(4)

factorielle(4) appelle factorielle(3)
├── factorielle(3) appelle factorielle(2)
│   ├── factorielle(2) appelle factorielle(1)
│   │   ├── factorielle(1) appelle factorielle(0)
│   │   │   └── factorielle(0) retourne 1 (cas de base)
│   │   └── factorielle(1) retourne 1 * 1 = 1
│   └── factorielle(2) retourne 2 * 1 = 2
└── factorielle(3) retourne 3 * 2 = 6
factorielle(4) retourne 4 * 6 = 24

Résultat final : 24

On peut également représenter la pile d'appels :

Étape	Pile d'appels	Action
1	`factorielle(4)`	Appel initial
2	`factorielle(4) → factorielle(3)`	Appel récursif
3	`factorielle(4) → factorielle(3) → factorielle(2)`	Appel récursif
4	`factorielle(4) → factorielle(3) → factorielle(2) → factorielle(1)`	Appel récursif
5	`factorielle(4) → factorielle(3) → factorielle(2) → factorielle(1) → factorielle(0)`	Appel récursif
6	`factorielle(4) → factorielle(3) → factorielle(2) → factorielle(1)`	factorielle(0) retourne 1
7	`factorielle(4) → factorielle(3) → factorielle(2)`	factorielle(1) retourne 1
8	`factorielle(4) → factorielle(3)`	factorielle(2) retourne 2
9	`factorielle(4)`	factorielle(3) retourne 6
10		factorielle(4) retourne 24

Définir une condition de base

Fondamental

L'importance de la condition de base

Définir une condition de base est une étape importante lors de la conception d'une fonction récursive pour éviter les boucles infinies.

La condition de base est une condition qui indique à la fonction récursive de sortir de l'appel récursif et de terminer l'exécution de manière appropriée. Cette condition doit être définie de manière à garantir que la fonction ne s'appelle pas elle-même indéfiniment.

Exemple : Fonction sans condition de base

À éviter : Récursion infinie

def recursif_infini(n):
    # Pas de condition de base !
    return n * recursif_infini(n-1)  # Appel récursif sans fin

# Cette fonction ne terminera jamais et provoquera une erreur de dépassement de pile
# recursif_infini(5)  # RecursionError: maximum recursion depth exceeded

Cette fonction s'appelle indéfiniment car il n'y a pas de condition d'arrêt. Python finira par lever une exception RecursionError après avoir atteint la limite de récursion (par défaut 1000).

Exemples de conditions de base bien définies

Factorielle

def factorielle(n):
    # Condition de base
    if n == 0:
        return 1
    return n * factorielle(n-1)

Condition : n == 0

Somme

def somme(n):
    # Condition de base
    if n == 1:
        return 1
    return n + somme(n-1)

Condition : n == 1

Fibonacci

def fibonacci(n):
    # Conditions de base
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Conditions : n == 0 ou n == 1

Puissance

def puissance(x, n):
    # Condition de base
    if n == 0:
        return 1
    return x * puissance(x, n-1)

Condition : n == 0

Caractéristiques d'une bonne condition de base

Accessible : On doit pouvoir l'atteindre après un nombre fini d'appels
Simple : Elle doit être résoluble directement (sans appel récursif)
Complète : Elle doit couvrir tous les cas d'arrêt possibles

Appels récursifs et empilement de la pile d'exécution

Définition : Pile d'exécution (call stack)

La pile d'exécution (ou call stack) est une structure de données qui enregistre les fonctions en cours d'exécution dans un programme. Chaque fois qu'une fonction est appelée, un cadre de pile (stack frame) est créé et empilé, contenant les variables locales, les paramètres et l'adresse de retour.

Lorsqu'une fonction récursive est appelée, elle s'exécute normalement jusqu'à ce qu'elle atteigne un point où elle appelle elle-même. À ce stade, une nouvelle instance de la fonction est créée et ajoutée à la pile d'exécution. La nouvelle instance commence alors son exécution à partir du début, tout en conservant les variables et les états de l'instance précédente.

Mécanisme

Le fonctionnement de la pile

Chaque appel récursif ajoute une nouvelle instance de la fonction à la pile d'exécution.
Lorsque la fonction atteint la condition de base et renvoie une valeur, cette valeur est retournée à l'appel précédent, qui continue son exécution là où il s'était arrêté.
Cela se poursuit jusqu'à ce que toutes les instances de la fonction aient été retirées de la pile d'exécution, et que la valeur finale soit renvoyée à l'appelant original.

Visualisation de la pile pour somme(5)

# État de la pile pendant l'exécution de somme(5)

Étape 1: Appel de somme(5)
Pile: [somme(5)]

Étape 2: somme(5) appelle somme(4)
Pile: [somme(5), somme(4)]

Étape 3: somme(4) appelle somme(3)
Pile: [somme(5), somme(4), somme(3)]

Étape 4: somme(3) appelle somme(2)
Pile: [somme(5), somme(4), somme(3), somme(2)]

Étape 5: somme(2) appelle somme(1)
Pile: [somme(5), somme(4), somme(3), somme(2), somme(1)]

Étape 6: somme(1) atteint la condition de base (n==1) et retourne 1
Pile: [somme(5), somme(4), somme(3), somme(2)]

Étape 7: somme(2) reçoit 1, calcule 2+1=3 et retourne 3
Pile: [somme(5), somme(4), somme(3)]

Étape 8: somme(3) reçoit 3, calcule 3+3=6 et retourne 6
Pile: [somme(5), somme(4)]

Étape 9: somme(4) reçoit 6, calcule 4+6=10 et retourne 10
Pile: [somme(5)]

Étape 10: somme(5) reçoit 10, calcule 5+10=15 et retourne 15
Pile: []

Risque : Dépassement de pile (stack overflow)

Il est important de comprendre que chaque appel récursif consomme de la mémoire en ajoutant une nouvelle instance de la fonction à la pile d'exécution. Si le nombre d'appels récursifs est trop important, cela peut entraîner une utilisation excessive de la mémoire et des erreurs de dépassement de pile.

Exemple avec une récursion trop profonde :

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

# Pour n très grand, cela peut causer un dépassement de pile
# recursif_profond(10000)  # RecursionError: maximum recursion depth exceeded

Python a une limite de récursion par défaut (généralement 1000) pour éviter de planter le système. On peut la modifier avec sys.setrecursionlimit(2000), mais cela n'élimine pas le problème fondamental de consommation mémoire.

Récursion vs Itération

Caractéristique	Récursion	Itération (boucles)
Définition	Une fonction s'appelle elle-même	Répétition d'un bloc d'instructions
Terminaison	Condition de base	Condition de continuation/arrêt
Mémoire	Consomme de la pile (O(n) en mémoire)	Espace constant (O(1) en mémoire)
Vitesse	Légèrement plus lente (appels de fonction)	Généralement plus rapide
Lisibilité	Plus élégante pour les problèmes récursifs naturels	Parfois plus complexe à comprendre
Cas d'usage	Arbres, graphes, fractales, algorithmes diviser-pour-régner	Parcours simples, calculs itératifs

Version itérative des exemples précédents

# Factorielle itérative
def factorielle_iterative(n):
    resultat = 1
    for i in range(1, n + 1):
        resultat *= i
    return resultat

# Somme itérative
def somme_iterative(n):
    resultat = 0
    for i in range(1, n + 1):
        resultat += i
    return resultat

# Tests
print(factorielle_iterative(5))  # 120
print(somme_iterative(100))       # 5050

Autres exemples classiques de récursivité

1. Suite de Fibonacci

def fibonacci(n):
    """
    Calcule le n-ième nombre de Fibonacci
    F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
    """
    # Conditions de base
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Appel récursif
    return fibonacci(n-1) + fibonacci(n-2)

print([fibonacci(i) for i in range(10)])  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Note sur Fibonacci

Cette version naïve de Fibonacci a une complexité exponentielle O(2ⁿ). Pour de grandes valeurs, elle devient extrêmement lente. C'est un bon exemple où la récursion naïve est inefficace et où des techniques comme la mémoisation (vue dans un cours précédent) sont nécessaires.

2. Parcours d'une structure arborescente

# Définition simple d'un arbre
class Noeud:
    def __init__(self, valeur, gauche=None, droite=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droite = droite

# Parcours récursif (préfixe)
def parcours_prefixe(noeud):
    if noeud is None:
        return
    
    print(noeud.valeur, end=' ')  # Visite la racine
    parcours_prefixe(noeud.gauche)  # Parcours sous-arbre gauche
    parcours_prefixe(noeud.droite)   # Parcours sous-arbre droit

# Création d'un arbre exemple
#        1
#       / \
#      2   3
#     / \
#    4   5
arbre = Noeud(1, 
              Noeud(2, Noeud(4), Noeud(5)),
              Noeud(3))

parcours_prefixe(arbre)  # 1 2 4 5 3

3. Recherche dichotomique récursive

def recherche_dichotomique_recursive(tableau, cible, debut, fin):
    """
    Recherche récursive d'un élément dans un tableau trié
    """
    # Condition de base : intervalle vide
    if debut > fin:
        return -1  # Élément non trouvé
    
    milieu = (debut + fin) // 2
    
    # Condition de base : élément trouvé
    if tableau[milieu] == cible:
        return milieu
    
    # Appels récursifs
    if tableau[milieu] < cible:
        return recherche_dichotomique_recursive(tableau, cible, milieu + 1, fin)
    else:
        return recherche_dichotomique_recursive(tableau, cible, debut, milieu - 1)

# Test
tableau = [1, 3, 5, 7, 9, 11, 13, 15]
print(recherche_dichotomique_recursive(tableau, 7, 0, len(tableau)-1))  # 3
print(recherche_dichotomique_recursive(tableau, 8, 0, len(tableau)-1))  # -1

Exercice pratique

La fonction puissance

Niveau : Débutant

Écrire une fonction récursive puissance(x, n) qui calcule xⁿ (x à la puissance n), où n est un entier positif ou nul.

Rappel mathématique :

x⁰ = 1 (pour tout x ≠ 0)
xⁿ = x × xⁿ⁻¹ (pour n > 0)

Exemples :

puissance(2, 3) → 8 (2³ = 2×2×2)
puissance(5, 0) → 1
puissance(3, 4) → 81

Solution

def puissance(x, n):
    """
    Calcule x à la puissance n de manière récursive
    
    Paramètres:
        x (int/float): La base
        n (int): L'exposant (entier positif ou nul)
        
    Retourne:
        int/float: xⁿ
    """
    # Condition de base : tout nombre à la puissance 0 vaut 1
    if n == 0:
        return 1
    
    # Appel récursif : x * xⁿ⁻¹
    return x * puissance(x, n - 1)

# Tests
print(puissance(2, 3))   # 8
print(puissance(5, 0))   # 1
print(puissance(3, 4))   # 81
print(puissance(10, 2))  # 100

# Version optimisée (diviser pour régner)
def puissance_optimisee(x, n):
    """
    Version plus efficace utilisant le principe :
    - Si n est pair : xⁿ = (xⁿ/²)²
    - Si n est impair : xⁿ = x × xⁿ⁻¹
    """
    if n == 0:
        return 1
    
    if n % 2 == 0:  # n pair
        moitie = puissance_optimisee(x, n // 2)
        return moitie * moitie
    else:  # n impair
        return x * puissance_optimisee(x, n - 1)

print(puissance_optimisee(2, 10))  # 1024
# Complexité: O(log n) au lieu de O(n)

Explication :

La condition de base est n == 0 (x⁰ = 1).
L'appel récursif suit la définition mathématique : xⁿ = x × xⁿ⁻¹.
La version optimisée utilise le principe de diviser pour régner pour une complexité logarithmique.

Bonnes pratiques pour la récursivité

Conseils pour écrire des fonctions récursives

Toujours définir une condition de base claire qui termine la récursion.
S'assurer que les appels récursifs convergent vers la condition de base (paramètres qui diminuent/augmentent).
Éviter la récursion excessive pour les problèmes avec profondeur importante (préférer l'itération ou la mémoisation).
Tester avec des cas simples pour vérifier le comportement.
Documenter clairement la condition de base et le principe de l'appel récursif.
Considérer l'optimisation (tail recursion, mémoisation) pour les cas complexes.

Points clés à retenir

Une fonction récursive est une fonction qui s'appelle elle-même.
Toute fonction récursive doit avoir une condition de base (cas d'arrêt) pour éviter les boucles infinies.
Chaque appel récursif ajoute un cadre à la pile d'exécution, consommant de la mémoire.
Une récursion trop profonde peut causer un dépassement de pile (stack overflow).
La récursivité est particulièrement adaptée aux structures de données récursives (arbres, listes chaînées) et aux algorithmes de type "diviser pour régner".
Certains problèmes ont des solutions récursives élégantes mais inefficaces (ex: Fibonacci) - dans ce cas, des optimisations comme la mémoisation sont nécessaires.
Il existe souvent un compromis entre récursion (élégance, clarté) et itération (performance, mémoire).

Rappel sur l'approche récursive

La récursivité : un concept fondamental

Premiers exemples de fonctions récursives

Exemple 1 : La fonction factorielle

Exemple 2 : La somme des n premiers nombres

Visualisation de l'exécution récursive

Définir une condition de base

L'importance de la condition de base

Exemple : Fonction sans condition de base

Exemples de conditions de base bien définies

Appels récursifs et empilement de la pile d'exécution

Le fonctionnement de la pile

Visualisation de la pile pour somme(5)

Récursion vs Itération

Version itérative des exemples précédents

Autres exemples classiques de récursivité

1. Suite de Fibonacci

2. Parcours d'une structure arborescente

3. Recherche dichotomique récursive

La fonction puissance

Bonnes pratiques pour la récursivité

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Rappel sur l'approche récursive

La récursivité : un concept fondamental

Premiers exemples de fonctions récursives

Exemple 1 : La fonction factorielle

Exemple 2 : La somme des n premiers nombres

Visualisation de l'exécution récursive

Définir une condition de base

L'importance de la condition de base

Exemple : Fonction sans condition de base

Exemples de conditions de base bien définies

Appels récursifs et empilement de la pile d'exécution

Le fonctionnement de la pile

Visualisation de la pile pour somme(5)

Récursion vs Itération

Version itérative des exemples précédents

Autres exemples classiques de récursivité

1. Suite de Fibonacci

2. Parcours d'une structure arborescente

3. Recherche dichotomique récursive

La fonction puissance

Bonnes pratiques pour la récursivité

Discussion (0)

Laisser un commentaire