Récursivité
Introduit| English | Sens |
|---|---|
| recursive/rɪˈkɜːsɪv/ | récursif |
| base case/beɪs keɪs/ | cas de base |
| recursive case/rɪˈkɜːsɪv keɪs/ | cas récursif |
| call stack/kɔːl stæk/ | pile d'appels |
| stack frame/stæk freɪm/ | trame de pile |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | débordement de pile |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | mémorisation |
Une définition qui se contient elle-même
- Comment dire ce qu'est un ancêtre ? Votre parent est un ancêtre. L'ancêtre de votre parent l'est aussi. Ces deux phrases définissent une chaîne illimitée, et la seconde utilise le mot qu'elle définit.
- Ce n'est pas un argument circulaire, car la première phrase donne à la chaîne quelque part où s'arrêter. Sans elle, la définition s'enlèverait à l'infini.
- Les programmes peuvent être écrits de la même manière, et pour les problèmes structurés comme cette chaîne, une solution récursive 递归 est considérablement plus courte qu'une boucle.
- Cette leçon porte sur le cas de base 基本情形 et le cas récursif 递归情形, la façon dont un appel récursif est tracé, et ce que fait le call stack 调用栈 en dessous.
Les deux cas
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- Le cas de base est une version du problème assez petite pour être résolue directement, sans appel supplémentaire. C'est ce qui arrête la récursion.
- Le cas récursif appelle la fonction à nouveau avec une entrée plus petite, se rapprochant du cas de base.
- Les deux sont requis. Une récursion sans cas de base ne s'arrête jamais ; une dont l'entrée ne diminue jamais ne atteint jamais le cas de base.
Every recursive algorithm must have a base case because:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Recursion is a natural fit for self-similar problems (trees, divide-and-conquer), but each call adds a stack frame — so without a base case it overflows the stack.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself.
What must a recursive routine have to terminate? Select tout that apply.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
A base case alone is not enough: if the input never shrinks, the base case is never reached and frames pile up until the stack overflows.
Exemple résolu : tracer une récursion
- Tracez
Factorial(4). - Enroulement :
Factorial(4)a besoin de4 * Factorial(3), qui a besoin de3 * Factorial(2), qui a besoin de2 * Factorial(1). Rien n'a encore été multiplié ; chaque appel est en attente. - Cas de base :
Factorial(1)retourne 1 sans appeler quoi que ce soit. - Unwinding (descente) :
2 * 1 = 2est retourné, puis3 * 2 = 6, puis4 * 6 = 24. - Montrez les deux sens. Un tracé qui ne descend ou ne remonte perd la moitié des points.
Recursion unwinds from the leaves up
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow.
What does Factorial(4) return?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
4 × 3 × 2 × 1 = 24.
Ce que la machine fait
- Chaque appel a besoin de sa propre copie de ses paramètres et variables locales, car
Factorial(3)etFactorial(2)sont des appels différents avec des valeurs différentes den. - Ces copies vivent dans une frame de pile 栈帧 sur la call stack : une frame par appel en cours, contenant les paramètres, les locales et l'adresse de retour.
- Une frame est pushée à chaque appel et popée quand elle retourne. C'est pourquoi les valeurs reviennent dans l'ordre inverse de celui des appels : la call stack est une pile, exactement l'ADT du chapitre 10.
Put the events of evaluating Factorial(4) in order.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
Ce qui peut mal tourner
- Pas de cas de base, ou un cas de base qui n'est jamais atteint : la récursion ne s'arrête jamais, les frames s'accumulent, et la call stack manque de mémoire. C'est une stack overflow 栈溢出.
- Récursion profonde : même une récursion correcte d'un million de niveaux a besoin d'un million de frames, elle peut donc épuiser la mémoire là où une boucle n'en utiliserait aucune.
- Travail répété : Fibonacci récursif naïf recalculer les mêmes valeurs exponentiellement souvent. Corrigez-le avec une boucle, ou avec la mémoïsation 记忆化, stockant chaque résultat la première fois qu'il est calculé.
Match each recursion term to what it means.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame.
A stack frame for a function call holds:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
Each call in progress keeps its parameters and locals in its own ____ on the call stack.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
Récursion ou itération
- La récursion convient aux problèmes auto-similaires, où le problème contient une copie plus petite de lui-même : traversal d'arbres, diviser pour régner comme la recherche dichotomique et merge sort, et la chaîne d'ancêtres ci-dessus.
- L'itération convient à tout le reste, et n'utilise aucune mémoire supplémentaire pour la répétition.
- Tout ce qui est récursif peut s'écrire itérativement et l'inverse est vrai. Le choix porte sur lequel exprime clairement le problème, pondéré contre la mémoire que coûte la pile.
A recursive routine crashes with a stack overflow. Which explanation is correct?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
Exemple résolu : énoncer les risques
- Un étudiant écrit une routine récursive et elle plante avec une stack overflow. Donnez deux causes possibles.
- Il n'y a pas de cas de base, ou le cas de base ne peut jamais être atteint car l'entrée ne diminue pas à chaque appel, donc les appels continuent à l'infini et les frames s'accumulent.
- La récursion est correcte mais trop profonde : chacun des très nombreux appels garde sa propre frame de pile, et la call stack manque de mémoire avant que le cas de base ne soit atteint.
- Les deux causes concernent l'accumulation de frames. Dites ce qui s'accumule et pourquoi cela ne s'arrête jamais.
Pièges qui font perdre des points
- Une récursion a besoin des deux : un cas de base et une entrée qui diminue. Nommérer uniquement le cas de base, c'est n'avoir que la moitié de la condition.
- Dans un tracé, montrez les appels winding up et les valeurs unwinding. Les deux sens rapportent des points.
- Chaque appel a ses propres paramètres et locales, dans sa propre frame de pile. C'est pourquoi la récursion coûte de la mémoire que l'itération n'a pas.
- Stack overflow est manquer de mémoire de pile à cause de trop de frames, pas un dépassement arithmétique.
Vous avez compris
- une routine récursive nécessite un cas de base résolu directement et un cas récursif qui s'appelle lui-même avec une entrée plus petite
- tracez-le dans les deux sens : appels montant jusqu'au cas de base, puis valeurs redescendant
- chaque appel a sa propre frame de pile sur la pile d'appels, poussée lors de l'appel et retirée lors du retour, ce qui explique pourquoi la récursion consomme de la mémoire
- risques : l'absence de cas de base atteignable entraîne une récursion infinie et un débordement de pile, la récursion profonde épuise la mémoire, et le travail répétitif nécessite une boucle ou une mémorisation