Qu'est-ce que la récursion ?

Question

Accepted Answer

**La récursion** est quand une fonction s'appelle elle-même pour résoudre une version plus petite du même problème. Chaque récursion a besoin d'un **cas de base** qui l'arrête et d'un **cas récursif** qui se rapproche du cas de base.

## L'idée

Décomposer un problème en sous-problèmes identiques plus petits. Chaque appel empile une frame sur la **pile d'appels** ; les retours les en enlèvent.

## Exemple

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Trace

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complexité

Ici **O(n)** en temps et **O(n)** d'espace de pile (une frame par appel).

## Pièges

- **Cas de base manquant** -> récursion infinie -> débordement de pile.
- Une récursion profonde peut épuiser la pile ; certains langages n'ont pas d'optimisation des appels terminaux.
- Recalculer des sous-problèmes qui se chevauchent peut exploser à un temps exponentiel (à corriger avec la mémoïsation).

## Pourquoi c'est important

La récursion exprime naturellement les problèmes auto-similaires — arbres, graphes, diviser pour régner — bien plus clairement que les boucles.

C'est le modèle mental derrière le tri fusion, le backtracking et la programmation dynamique.

Comprendre la pile d'appels vous rend aussi meilleur pour déboguer et raisonner sur la mémoire.