Recursion: base case and recursive case
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.
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.
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;
}
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.
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.
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
Calls split to a base case, then values return up.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do não write a main.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 é 1, otherwise base * power(base, exp - 1). Do não write a main.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
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 decrescentes 0. Do não write a main.
Clique em Executar para ver a saída aqui.