Recursion: base case and recursive case · Recursão: caso base e caso recursivo
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
Uma função que se chama
- Recursão é quando uma função chama ela mesma para resolver uma versão menor do mesmo problema.
- Precisa de duas partes: um caso base que para, e um caso recursivo que reduz o problema.
- Sem um caso base, chamaria a si mesma para sempre e travaria.
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
O caso base
- O caso base é o menor problema que você pode responder diretamente, sem mais chamadas.
- Para fatorial,
0!e1!são ambos1— esse é o caso base. - Sempre trate o caso base primeiro, para que a recursão tenha onde parar.
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
O caso recursivo
- O caso recursivo resolve o problema usando a resposta de um menor.
n! = n × (n - 1)!, entãofactorial(n)retornan * factorial(n - 1).- Cada chamada deve se mover mais perto do caso base, ou nunca parará.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
Recursão sobre um array
- Você pode fazer recursão ao longo de um array passando um índice que avança a cada chamada.
- O caso base é "o índice chegou ao final" (retornar
0para uma soma). - O caso recursivo é
a[i] + sum(a, i + 1, n)— este item mais a soma do restante.
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
Erros comuns
- A recursão precisa de um caso base, senão a pilha de chamadas transborda.
- Cada chamada deve se aproximar do caso base.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
Agora você tenta
- Escreva o caso base primeiro, depois o caso recursivo que se chama com uma entrada menor.
- Mantenha os valores de teste pequenos para que os números fiquem dentro de um
int. - Não escreva um
main— o verificador fornece um.
Recursion returns up · Recursão retorna para cima
Calls split to a base case, then values return up. · Chamadas dividem para um caso base, então valores retornam para cima.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not · não write a main. · Complete int factorial(int n) usando recursão: retorne 1 para n <= 1 (o caso base), caso contrário n * factorial(n - 1). Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not · não write a main. · Complete int power(int base, int exp) usando recursão (assuma exp >= 0): base elevado a 0 é 1, caso contrário base * power(base, exp - 1). Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns · decrescentes 0. Do not · não write a main. · Complete int array_sum(const int a[], int i, int n) usando recursão: ele retorna a soma de a[i] até a[n-1]. Caso base: i >= n retorna 0. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.