Récursivité
Définir un problème par ses sous-problèmes plus simples, jusqu’au cas de base.
1
Principe
Définition
La récursivité définit un problème par une version plus simple de lui-même.
- Cas de base pour arrêter.
- Appel récursif vers un sous-problème.
Structure
2
Arrêt
Cas de base et terminaison
- 1
Identifier le cas de base.
- 2
Réduire la taille du problème.
- 3
Revenir au cas de base.
Pièges
Sans cas de base, la récursion continue indéfiniment.
3
Mémoire
Pile d’appels
| Élément | Rôle |
|---|---|
| Cadre d’appel | Stocke paramètres et variables. |
| Pile | Empile les appels en cours. |
| Retour | Dépile dans l’ordre inverse. |
4
Déroulement
Exemple concret
Factorielle de 4, avec cas de base n = 0.
- 4! appelle 3!
- 3! appelle 2!
- 2! appelle 1!
4! se calcule par retours successifs des appels.
Exemples classiques
- Factorielle : un seul sous-problème.
- Fibonacci : deux appels récursifs.
5
Comparaison
Récursif
Récursif
- Expression naturelle sur arbres.
- Code souvent plus court.
- Pile d’appels consommée.
Itératif
- Utilise boucles et contrôle.
- Souvent plus économe en mémoire.
- Parfois plus simple à optimiser.
Coût
La pile d’appels ajoute un surcoût mémoire, même si le temps peut rester comparable.
À retenir
Résumé
- Le cas de base arrête la récursion.
- L’appel récursif réduit le problème.
- La pile d’appels gère les retours.
- La terminaison dépend de la progression.