Recursão
Introduzido| English | Significado |
|---|---|
| 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/ | memorização |
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.
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:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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 todos that apply.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
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
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?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
4 × 3 × 2 × 1 = 24.
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.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
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.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
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.
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.
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