Raisonner récursivement : base et récursion
Décomposer un problème en copies plus petites
Raisonner récursivement : base et récursion est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Ce que signifie la récursivité
La récursivité est une fonction qui résout un problème en s’appelant elle-même sur une partie plus petite, jusqu’à ce que cette partie soit suffisamment petite pour recevoir une réponse directe. 🌀
Faites confiance à la version plus petite
L’état d’esprit essentiel est le saut de confiance : supposez que l’appel récursif fonctionne déjà sur l’entrée plus petite, puis construisez votre réponse à partir de là.
Toute récursivité a besoin d’un cas de base
Le cas de base est la plus petite entrée à laquelle vous répondez sans récursivité. Sans lui, la fonction s’appelle indéfiniment et finit par planter.
Le cas récursif
Le cas récursif réduit le problème et s’appelle lui-même sur une version plus petite. Chaque appel doit se rapprocher du cas de base.
La factorielle comme premier exemple
Ici, la factorielle montre les deux éléments : un cas de base à zéro et un appel récursif sur n moins un.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)Fonctionnement de la pile d'appels
Chaque appel attend dans la pile d'appels jusqu'au retour de son appel interne. L'appel le plus profond se termine en premier, puis les résultats remontent progressivement.
Surveillez la profondeur de récursion
Par défaut, Python limite la profondeur de récursion à environ 1 000. Une récursivité profonde en concours nécessite sys.setrecursionlimit pour éviter une erreur d'exécution.
import sys
sys.setrecursionlimit(300000)Progressez à chaque appel
Une récursivité correcte réduit toujours l'entrée jusqu'au cas de base. Si elle repasse un jour par une entrée de même taille, elle boucle indéfiniment. ⚠️
Additionnez récursivement une liste
Cette somme récursive retire le premier élément, puis s'en remet à l'appel pour additionner le reste de la liste.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Les arbres de récursivité montrent les embranchements
Lorsqu'une fonction effectue plusieurs appels, le travail forme un arbre de récursivité. Sa taille indique le coût total.
Le travail répété peut ralentir
La suite de Fibonacci naïve recalcule les mêmes valeurs encore et encore, ce qui donne un temps exponentiel. Mémoriser ces résultats règle immédiatement le problème.
Vérification rapide
Que se passe-t-il si une fonction récursive n'a pas de cas de base ?
Récapitulatif : deux parties, une idée
Vous avez appris que la récursivité a besoin d'un cas de base pour s'arrêter et d'un cas récursif qui réduit l'entrée. Faites confiance à l'appel plus petit, et le reste suivra. 🎯
Questions Fréquemment Posées
La leçon « Raisonner récursivement : base et récursion » est-elle gratuite ?
Oui — le texte complet de « Raisonner récursivement : base et récursion » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Raisonner récursivement : base et récursion » ?
Décomposer un problème en copies plus petites Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Raisonner récursivement : base et récursion » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Raisonner récursivement : base et récursion
- Générer tous les sous-ensembles
- Permutations et idée des N reines
- Élaguer pour respecter la limite de temps