Recursion · Recursão
| English | Português |
|---|---|
| recursive/rɪˈkɜːsɪv/ | recursivo |
| base case/beɪs keɪs/ | caso base |
| recursive case/rɪˈkɜːsɪv keɪs/ | caso recursivo |
| call stack/kɔːl stæk/ | pilha de chamadas |
| stack frame/stæk freɪm/ | quadro de pilha |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | estouro de pilha |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | memoização |
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.
Uma definição que contém a si mesma
- Como dizer o que é um ancestral? Seu pai é um ancestral. E o ancestral do seu pai também. Essas duas frases definem uma cadeia ilimitada, e a segunda usa a palavra que está definindo.
- Isso não é um argumento circular, porque a primeira frase dá à cadeia um ponto de parada. Sem ela, a definição se desenrolaria para sempre.
- Programas podem ser escritos dessa mesma forma, e para problemas moldados como essa cadeia, uma solução recursiva 递归 é drasticamente menor que um loop.
- Esta aula é sobre o caso base 基本情形 e o caso recursivo 递归情形, como rastrear uma chamada recursiva e o que a call stack 调用栈 está fazendo por baixo.
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.
Os dois casos
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
- O caso base é uma versão do problema pequena o suficiente para responder diretamente, sem chamada adicional. É o que para a recursão.
- O caso recursivo chama a função novamente com uma entrada menor, aproximando-se do caso base.
- Ambos são necessários. Uma recursão sem caso base nunca para; uma cuja entrada não diminui nunca atinge o caso base.
Every recursive algorithm must have a base case because: · Todo algoritmo recursivo deve ter um caso base porque:
The base case is the condition that ends the chain of calls; without it the recursion runs forever. · O caso base é a condição que termina a cadeia de chamadas; sem ele a recursão roda para sempre.
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. · A recursão é um ajuste natural para problemas auto-similares (árvores, divide-and-conquer), mas cada chamada adiciona um frame de pilha — então sem um caso base ela transborda a pilha.
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself. · Um loop de contagem simples é mais limpo para iteração comum; a recursão brilha quando o problema contém cópias menores dele mesmo.
What must a recursive routine have to terminate? Select all · todos that apply. · O que uma rotina recursiva deve ter para terminar? Selecione todas as que se aplicam.
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. · Um caso base sozinho não é suficiente: se a entrada nunca encolher, o caso base nunca é atingido e frames se acumulam até a pilha transbordar.
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.
Exemplo resolvido: rastreie uma recursão
- Rastreie
Factorial(4). - Enrolando:
Factorial(4)precisa de4 * Factorial(3), que precisa de3 * Factorial(2), que precisa de2 * Factorial(1). Nada foi multiplicado ainda; cada chamada está esperando. - Caso base:
Factorial(1)retorna 1 sem chamar nada. - Desenrolando:
2 * 1 = 2é retornada, depois3 * 2 = 6, depois4 * 6 = 24. - Mostre ambas as direções. Um rastro que só desce ou só sobe perde metade das notas.
Recursion unwinds from the leaves up · A recursão desenrola das folhas para cima
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. · Passo a passo de fib(4) na ordem em que as chamadas realmente terminam: as folhas (casos base) resolvem primeiro, depois cada pai combina seus filhos. Note que fib(2) é calculado duas vezes — esse trabalho repetido é por que a recursão ingênua é lenta.
What does Factorial(4) return? · O que Factorial(4) retorna?
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.
O que a máquina está fazendo
- Cada chamada precisa de sua própria cópia de seus parâmetros e variáveis locais, porque
Factorial(3)eFactorial(2)são chamadas diferentes com valores diferentes den. - Essas cópias vivem em um stack frame 栈帧 na call stack: um frame por chamada em andamento, segurando parâmetros, locais e endereço de retorno.
- Um frame é empilhado em cada chamada e removido ao retornar. É por isso que os valores voltam na ordem inversa à que foram chamados: a call stack é uma pilha, exatamente a ADT do tópico 10.
Put the events of evaluating Factorial(4) in order. · Coloque os eventos de avaliar Factorial(4) em ordem.
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds. · Nada é multiplicado ao descer; cada chamada espera. As multiplicações ocorrem todas quando a pilha está sendo desempilhada.
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.
O que dá errado
- Sem caso base, ou um caso base que nunca é atingido: a recursão nunca para, frames se acumulam e a call stack fica sem memória. Isso é um stack overflow 栈溢出.
- Recursão profunda: mesmo uma recursão correta de um milhão de níveis precisa de um milhão de frames, então pode esgotar memória onde um loop usaria nenhuma.
- Trabalho repetitivo: Fibonacci recursivo ingênuo recalcula os mesmos valores exponencialmente muitas vezes. Corrija com um loop ou com memoização 记忆化, armazenando cada resultado na primeira vez que é calculado.
Match each recursion term to what it means. · Combine cada termo de recursão com o seu significado.
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame. · Uma recursão precisa de um caso base para parar e um caso recursivo para reduzir o problema; cada chamada adiciona um quadro de pilha.
A stack frame for a function call holds: · Um quadro de pilha para uma chamada de função armazena:
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other. · Cada quadro armazena os parâmetros, as variáveis locais e onde retomar daquela chamada — para que as chamadas não se sobreponham.
Each call in progress keeps its parameters and locals in its own ____ on the call stack. · Cada chamada em andamento mantém seus parâmetros e variáveis locais em sua própria ____ na pilha de chamadas.
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made. · Empilhado na chamada, desempilhado no retorno. É por isso que os valores retornam na ordem inversa àquela em que as chamadas foram feitas.
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.
Recursão ou iteração
- Recursão se adapta a problemas auto-similares, onde o problema contém uma cópia menor dele mesmo: traversia de árvore, divide e conquista como busca binária e merge sort, e a cadeia de ancestrais acima.
- Iteração se adapta a tudo o mais, e usa nenhuma memória extra para a repetição.
- Tudo recursivo pode ser escrito iterativamente e vice-versa. A escolha é sobre qual expressa o problema claramente, ponderado contra a memória que a pilha custa.
A recursive routine crashes with a stack overflow. Which explanation is correct? · Uma rotina recursiva falha com estouro de pilha. Qual explicação está correta?
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely. · Estouro de pilha trata-se de quadros, não de aritmética. Um número muito grande para seu registrador é um estouro aritmético, algo totalmente diferente.
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.
Exemplo resolvido: declare os riscos
- Um aluno escreve uma rotina recursiva e ela falha com stack overflow. Dê duas causas possíveis.
- Não há caso base, ou o caso base nunca pode ser atingido porque a entrada não fica menor a cada chamada, então as chamadas continuam para sempre e frames se acumulam.
- A recursão está correta mas muito profunda: cada uma das muitas chamadas mantém seu próprio frame de pilha, e a call stack fica sem memória antes que o caso base seja atingido.
- Ambas as causas são sobre frames se acumulando. Diga o que se acumula e por que não para nunca.
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.
Marcas que escapam
- Uma recursão precisa de ambos um caso base e uma entrada que fique menor. Nomear apenas o caso base é metade da condição.
- Em um rastro, mostre as chamadas enrolando e os valores desenrolando. Ambas as direções carregam notas.
- Cada chamada tem seus próprios parâmetros e locais, em seu próprio stack frame. É por isso que recursão custa memória que iteração não custa.
- Stack overflow é ficar sem memória de pilha devido a muitos frames, não um overflow aritmético.
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
Entendeu?
- uma rotina recursiva precisa de um caso base resolvido diretamente e um caso recursivo que se chame com uma entrada menor
- rastreie em ambas as direções: chamadas enrolando até o caso base, depois valores desenrolando de volta
- cada chamada tem seu próprio stack frame na call stack, empilhado na chamada e removido no retorno, que é por isso que recursão custa memória
- riscos: a ausência de um caso base alcançável causa recursão infinita e estouro de pilha (stack overflow), recursão profunda esgota a memória, e trabalho repetitivo exige um loop ou memoização