Recursion · Récursivité
| English | Français |
|---|---|
| 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épassement de pile |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | mémorisation |
A definition that contains itself
- How do you say what an ancestor is? Your parent is an ancestor. So is your parent's ancestor. Those two sentences define an unbounded chain, and the second one uses the word it is defining.
- That is not a circular argument, because the first sentence gives the chain somewhere to stop. Without it, the definition would unwind for ever.
- Programs can be written the same way, and for problems shaped like that chain, a recursive 递归 solution is dramatically shorter than a loop.
- This lesson is the base case 基本情形 and the recursive case 递归情形, how a recursive call is traced, and what the call stack 调用栈 is doing underneath.
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.
The two cases
- The base case is a version of the problem small enough to answer directly, with no further call. It is what stops the recursion.
- The recursive case calls the function again with a smaller input, moving towards the base case.
- Both are required. A recursion with no base case never stops; one whose input does not shrink never reaches the base case.
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: · Tout algorithme récursif doit avoir un cas de base parce que :
The base case is the condition that ends the chain of calls; without it the recursion runs forever. · Le cas de base est la condition qui met fin à la chaîne d'appels ; sans lui, la récursivité tourne à l'infini.
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. · La récursivité est un bon choix pour les problèmes auto-similaires (arbres, diviser pour régner), mais chaque appel ajoute une frame de pile — donc sans cas de base, elle déborde la pile.
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself. · Une boucle de comptage simple est plus propre pour une itération classique ; la récursivité brille lorsque le problème contient des copies plus petites de lui-même.
What must a recursive routine have to terminate? Select all · tout that apply. · Que doit avoir une routine récursive pour se terminer ? Sélectionnez toutes les options qui s'appliquent.
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. · Un cas de base seul ne suffit pas : si l'entrée ne diminue jamais, le cas de base n'est jamais atteint et les frames s'empilent jusqu'à ce que la pile déborde.
Worked example: trace a recursion
- Trace
Factorial(4). - Winding up:
Factorial(4)needs4 * Factorial(3), which needs3 * Factorial(2), which needs2 * Factorial(1). Nothing has been multiplied yet; each call is waiting. - Base case:
Factorial(1)returns 1 without calling anything. - Unwinding:
2 * 1 = 2is returned, then3 * 2 = 6, then4 * 6 = 24. - Show both directions. A trace that only goes down, or only comes back, loses half the marks.
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 · La récursivité se déroule depuis les feuilles vers le haut
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. · Parcourir fib(4) dans l'ordre où les appels se terminent réellement : les feuilles (cas de base) se résolvent d'abord, puis chaque parent combine ses enfants. Remarquez que fib(2) est calculé deux fois — ce travail répété explique pourquoi la récursivité naïve est lente.
What does Factorial(4) return? · Que retourne Factorial(4) ?
4 × 3 × 2 × 1 = 24.
What the machine is doing
- Every call needs its own copy of its parameters and local variables, because
Factorial(3)andFactorial(2)are different calls with different values ofn. - Those copies live in a stack frame 栈帧 on the call stack: one frame per call in progress, holding the parameters, the locals and the return address.
- A frame is pushed on each call and popped when it returns. That is why the values come back in the reverse of the order they were called: the call stack is a stack, exactly the ADT from topic 10.
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. · Placez les événements d'évaluation de Factorial(4) dans l'ordre.
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds. · Rien n'est multiplié lors de la descente ; chaque appel attend. Les multiplications se produisent toutes pendant le déroulement de la pile.
What goes wrong
- No base case, or a base case that is never reached: the recursion never stops, frames pile up, and the call stack runs out of memory. That is a stack overflow 栈溢出.
- Deep recursion: even a correct recursion of a million levels needs a million frames, so it can exhaust memory where a loop would use none.
- Repeated work: naive recursive Fibonacci recomputes the same values exponentially many times. Fix it with a loop, or with memoisation 记忆化, storing each result the first time it is computed.
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. · Faites correspondre chaque terme de récursion à sa signification.
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame. · Une récursion nécessite un cas de base pour s'arrêter et un cas récursif pour réduire le problème ; chaque appel ajoute une trame de pile.
A stack frame for a function call holds: · Une trame de pile pour un appel de fonction contient :
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other. · Chaque trame stocke les paramètres, variables locales et l'endroit où reprendre cet appel — ainsi les appels ne se chevauchent pas.
Each call in progress keeps its parameters and locals in its own ____ on the call stack. · Chaque appel en cours conserve ses paramètres et variables locales dans sa propre ____ sur la pile d'appels.
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made. · Empilée lors de l'appel, dépilee lors du retour. C'est pourquoi les valeurs reviennent dans l'ordre inverse de celui des appels.
Recursion or iteration
- Recursion suits self-similar problems, where the problem contains a smaller copy of itself: tree traversal, divide and conquer such as binary search and merge sort, and the ancestor chain above.
- Iteration suits everything else, and uses no extra memory for the repetition.
- Anything recursive can be written iteratively and the reverse is also true. The choice is about which one expresses the problem clearly, weighed against the memory the stack costs.
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? · Une routine récursive plante avec un débordement de pile. Quelle explication est correcte ?
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely. · Le débordement de pile concerne les trames, pas l'arithmétique. Un nombre trop grand pour son registre est un dépassement arithmétique, une chose tout à fait différente.
Worked example: state the risks
- A student writes a recursive routine and it crashes with a stack overflow. Give two possible causes.
- There is no base case, or the base case can never be reached because the input does not get smaller on each call, so calls continue for ever and frames accumulate.
- The recursion is correct but too deep: each of the very many calls keeps its own stack frame, and the call stack runs out of memory before the base case is reached.
- Both causes are about frames accumulating. Say what accumulates and why it never stops.
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.
Marks that slip away
- A recursion needs both a base case and an input that gets smaller. Naming only the base case is half the condition.
- In a trace, show the calls winding up and the values unwinding. Both directions carry marks.
- Each call has its own parameters and locals, in its own stack frame. That is why recursion costs memory that iteration does not.
- Stack overflow is running out of stack memory from too many frames, not an arithmetic overflow.
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.
You've got it
- a recursive routine needs a base case solved directly and a recursive case that calls itself with a smaller input
- trace it in both directions: calls winding up to the base case, then values unwinding back
- each call has its own stack frame on the call stack, pushed on call and popped on return, which is why recursion costs memory
- risks: no reachable base case gives infinite recursion and stack overflow, deep recursion exhausts memory, and repeated work needs a loop or memoisation
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