Recursion · Recursão
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Esta página precisa de um navegador recente (com suporte a SharedArrayBuffer). Por favor, atualize Chrome, Edge, Firefox ou Safari para a versão mais recente.
English
A function that calls itself
- Recursion is when a function calls itself.
- Each call should work on a smaller version of the problem.
- Done right, the problem shrinks until it is trivial to solve.
Português
Uma função que se chama
- Recursion é quando uma função se chama ela mesma.
- Cada chamada deve trabalhar em uma versão menor do problema.
- Quando feito corretamente, o problema diminui até se tornar trivial de resolver.
English
Base case and recursive case
- The base case is the simplest case — it stops the recursion.
- The recursive case calls the function again on a smaller input.
- Without a base case the function never stops (an error).
Português
Caso base e caso recursivo
- O caso base é o caso mais simples — ele interrompe a recursão.
- O caso recursivo chama a função novamente com uma entrada menor.
- Sem um caso base, a função nunca para (um erro).
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
English
A worked example: factorial
- The factorial
n!meansn × (n-1) × ... × 1. - In recursive form:
n! = n × (n-1)!, and the base case is0! = 1. - Each call multiplies
nby the factorial of one less.
Português
Um exemplo resolvido: fatorial
- O fatorial
n!significan × (n-1) × ... × 1. - Na forma recursiva:
n! = n × (n-1)!, e o caso base é0! = 1. - Cada chamada multiplica
npelo fatorial de um a menos.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
English
How the computer runs it
- Each call is paused on a call stack while it waits for the inner call.
- When the base case returns, the paused calls finish one by one.
- Too many calls overflow the stack — Python raises a
RecursionError.
Português
Como o computador o executa
- Cada chamada é pausada em uma pilha de chamadas enquanto aguarda a chamada interna.
- Quando o caso base retorna, as chamadas pausadas terminam uma por uma.
- Muitas chamadas excessivas transbordam a pilha — Python levanta um
RecursionError.
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
Português
Em pseudocódigo do Cambridge
- Uma função recursiva nomeia claramente seu caso base e caso recursivo.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
English
Common mistakes
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
Português
Erros comuns
- Toda recursão precisa de um caso base, ou ela transborda a pilha de chamadas.
- Cada chamada deve se aproximar do caso base.
English
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
Português
Agora você tenta
- Dê a cada função um caso base e um caso recursivo.
- Clique em Check answer para testar seu código.
Explore · Explorar
Recursion returns from the leaves · Recursão retorna das folhas
Each call splits into smaller calls; answers return up from the base cases. · Cada chamada divide em chamadas menores; respostas retornam para cima dos casos base.
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · Escreva uma recursiva sum_to(n) que retorna 1 + 2 + ... + n. O caso base é sum_to(0) que é 0.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · Escreva uma recursiva power(base, exp) que retorna base elevado a exp. O caso base é exp == 0, que dá 1.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list []. · Escreva uma recursiva count_up(n) que retorna a lista [1, 2, ..., n]. O caso base é count_up(0) que é a lista vazia [].
Click Run to see the output here. · Clique em Executar para ver a saída aqui.