🎯 Objectifs de la lecon
- •Définir une fonction récursive et identifier ses composantes
- •Expliquer la terminaison d'une fonction récursive et le rôle de la condition d'arrêt
- •Comparer les approches récursive et itérative sur des exemples simples
La récursivité est une technique de programmation où une fonction s'appelle elle-même pour résoudre un problème en le divisant en sous-problèmes plus simples. Elle est très utilisée en algorithmique pour traiter des structures comme les arbres ou les listes.
Définition d'une fonction récursive
Une fonction récursive est une fonction qui s'appelle elle-même dans son propre corps. Chaque appel récursif doit résoudre un sous-problème plus petit que le problème initial.
Une fonction récursive comporte deux parties essentielles : un cas de base (ou condition d'arrêt) qui stoppe la récursion, et un ou plusieurs appels récursifs qui réduisent la taille du problème.
« Exemple : la fonction factorielle. factorielle(5) = 5 × factorielle(4). Ici, factorielle(4) est un appel récursif. Le cas de base est factorielle(0) = 1. »
Point fort : Montre clairement la réduction du problème : de n à n-1, jusqu'à atteindre 0.
✔️ A retenir
Une fonction récursive s'appelle elle-même. Elle doit toujours avoir un cas de base pour éviter une boucle infinie.
Exemples de fonctions récursives
Voici deux exemples classiques : le calcul de la factorielle et la somme des entiers de 1 à n.
Pour la factorielle : def factorielle(n): if n == 0: return 1 else: return n * factorielle(n-1). Le cas de base est n == 0.
Pour la somme des entiers : def somme(n): if n == 0: return 0 else: return n + somme(n-1). Le cas de base est n == 0.
⚠️ Attention
Attention : si tu oublies le cas de base, la fonction s'appelle indéfiniment et provoque une erreur de dépassement de pile (RecursionError).
Terminaison et condition d'arrêt
La terminaison d'une fonction récursive garantit qu'elle s'arrête après un nombre fini d'appels. Elle dépend de la condition d'arrêt et de la réduction du problème à chaque appel.
Pour qu'une fonction récursive termine, il faut : 1) un cas de base qui ne fait pas d'appel récursif, 2) que chaque appel récursif se rapproche du cas de base (par exemple en diminuant un entier).
« Exemple : factorielle(3) appelle factorielle(2), puis factorielle(1), puis factorielle(0) qui renvoie 1. La chaîne d'appels s'arrête. »
Point fort : Illustre la progression vers le cas de base et l'arrêt effectif.
✔️ A retenir
Toute fonction récursive doit avoir une condition d'arrêt. Chaque appel récursif doit réduire la taille du problème pour garantir la terminaison.
Récursivité vs itération
Un même problème peut souvent être résolu de manière récursive ou itérative (avec des boucles). Les deux approches ont des avantages et des inconvénients.
Avantages de la récursivité : code plus court et plus lisible pour des problèmes naturellement récursifs (parcours d'arbre, fractales). Inconvénients : consommation mémoire plus élevée (pile d'appels) et risque de dépassement de pile.
Avantages de l'itération : généralement plus efficace en mémoire et en temps, pas de risque de dépassement de pile. Inconvénients : code parfois plus long et moins intuitif pour des structures récursives.
« Exemple : factorielle en itératif : def factorielle_iter(n): res = 1 ; for i in range(1, n+1): res *= i ; return res. Même résultat, approche différente. »
Point fort : Montre la différence de style : récursif utilise l'appel à soi-même, itératif utilise une boucle.
✔️ A retenir
La récursivité simplifie l'écriture de certains algorithmes mais utilise plus de mémoire. L'itération est souvent plus efficace. Choisis selon le problème et les contraintes.
Erreurs fréquentes
Erreur 1 : oublier le cas de base. La fonction s'appelle indéfiniment et provoque une RecursionError. Exemple : def f(n): return f(n-1) sans condition.
Erreur 2 : ne pas réduire le problème. Si l'appel récursif ne modifie pas l'argument, la fonction ne termine jamais. Exemple : def f(n): if n==0: return 0 else: return f(n).
Erreur 3 : confondre récursivité et itération dans la même fonction. Par exemple, utiliser une boucle à l'intérieur d'une fonction récursive peut compliquer la logique.
⚠️ Attention
Attention : une fonction récursive qui ne termine pas peut faire planter ton programme. Vérifie toujours la condition d'arrêt et la progression.
Mini-quiz
Question 1 : Quelle est la condition d'arrêt de la fonction factorielle ? Réponse : n == 0.
Question 2 : Vrai ou faux ? Une fonction récursive peut s'appeler elle-même sans condition d'arrêt. Réponse : Faux, elle ne terminerait pas.
Question 3 : Cite un avantage de l'itération par rapport à la récursivité. Réponse : Moins de consommation mémoire.
