Reunimos 12 exercícios em que você escreve funções recursivas (funções que chamam a si mesmas), do nível iniciante ao avançado. A função main já está pronta: você só precisa escrever o corpo da função pedida. O objetivo é resolver com recursão, sem usar laços. Ao clicar em "Corrigir", seu código é testado com várias entradas usando gcc de verdade, e a saída é conferida.
Obs.: Executar e Corrigir enviam seu código ao Wandbox, um serviço externo e gratuito de compilação, que o executa com gcc.
int sum_to(int n), que recebe um inteiro n ≥ 0 (0 ≤ n ≤ 1000) e retorna a soma de 1 até n, usando recursão, sem laços. Quando n é 0, retorne 0. A função main já está pronta."Executar" roda seu código com a entrada acima. "Corrigir" testa com 4 entradas preparadas.
return sum_to(n - 1) + n;. Só isso nunca para, então escreva antes a condição de parada: quando n == 0, retorne 0.#include <stdio.h> int sum_to(int n) { if (n == 0) { return 0; } return sum_to(n - 1) + n; } int main(void) { int n; scanf("%d", &n); printf("Soma: %d\n", sum_to(n)); return 0; }
long long power(int x, int n), que recebe um inteiro x (−9 ≤ x ≤ 9) e um inteiro n ≥ 0 (0 ≤ n ≤ 18) e retorna x elevado a n. Considere x0 = 1 (inclusive 00 = 1). A função main já está pronta."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
n == 0, retorne 1; caso contrário, return x * power(x, n - 1);.#include <stdio.h> long long power(int x, int n) { if (n == 0) { return 1; } return x * power(x, n - 1); } int main(void) { int x, n; scanf("%d %d", &x, &n); if (x < 0) printf("(%d)^%d = %lld\n", x, n, power(x, n)); else printf("%d^%d = %lld\n", x, n, power(x, n)); return 0; }
long long. Em x * power(...), x é convertido para long long antes da multiplicação.int count_digits(int n), que recebe um inteiro n ≥ 0 (0 ≤ n ≤ 2000000000) e retorna quantos dígitos ele tem. Considere que 0 tem 1 dígito. A função main já está pronta."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
n < 10), retorne 1. Caso contrário, a resposta é o número de dígitos de n / 10 (n sem o dígito das unidades) mais 1.#include <stdio.h> int count_digits(int n) { if (n < 10) { return 1; } return 1 + count_digits(n / 10); } int main(void) { int n; scanf("%d", &n); printf("Dígitos: %d\n", count_digits(n)); return 0; }
n == 0 retorna 0", a entrada 0 fica com 0 dígitos. Para decidir em que valor parar, confira se a resposta está certa para a menor entrada possível (aqui, 0).int fib(int n), que retorna o n-ésimo número de Fibonacci, definido por F(0) = 0, F(1) = 1 e F(n) = F(n−1) + F(n−2) (0 ≤ n ≤ 30). A função main já está pronta."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
n == 0, retorne 0; se n == 1, retorne 1; caso contrário, return fib(n - 1) + fib(n - 2);.#include <stdio.h> int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); } int main(void) { int n; scanf("%d", &n); printf("fib(%d) = %d\n", n, fib(n)); return 0; }
fib(1) chama fib(-1) e nunca para. Além disso, esse jeito de escrever repete os mesmos cálculos muitas vezes, então a quantidade de trabalho cresce cerca de 1,6 vez a cada aumento de 1 em n (com n=30, são cerca de 2,7 milhões de chamadas).void print_reverse(const char s[], int i), que recebe uma string s e uma posição i e mostra de trás para frente os caracteres de s[i] até o fim da string. A função main já está pronta: ela lê uma string sem espaços, de letras, dígitos e símbolos (até 100 caracteres), chama print_reverse(s, 0) e no final pula uma linha."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
s[i] for o caractere terminador '\0', volte sem fazer nada. Caso contrário, primeiro mostre o resto ao contrário com print_reverse(s, i + 1) e depois mostre s[i].#include <stdio.h> void print_reverse(const char s[], int i) { if (s[i] == '\0') { return; } print_reverse(s, i + 1); printf("%c", s[i]); } int main(void) { char s[101]; scanf("%100s", s); print_reverse(s, 0); printf("\n"); return 0; }
printf vier antes da chamada recursiva, os caracteres aparecem na ordem original. Se vier depois, eles aparecem na ordem em que as chamadas retornam, a partir da mais profunda (o último caractere), ou seja, ao contrário.void print_binary(int n), que recebe um inteiro n ≥ 0 (0 ≤ n ≤ 1000000000) e o mostra em binário. Não coloque zeros extras à esquerda. 0 deve ser mostrado como 0. A função main já está pronta e pula uma linha depois de chamar a função."Executar" roda seu código com a entrada acima. "Corrigir" testa com 6 entradas preparadas.
n % 2, e os dígitos acima dele são o binário de n / 2. Como queremos mostrar a partir dos dígitos mais altos, se n >= 2, chame primeiro print_binary(n / 2) e depois mostre n % 2.#include <stdio.h> void print_binary(int n) { if (n >= 2) { print_binary(n / 2); } printf("%d", n % 2); } int main(void) { int n; scanf("%d", &n); print_binary(n); printf("\n"); return 0; }
n == 0, não faz nada", nada é mostrado quando a entrada é 0.int array_max(const int a[], int n), que retorna o maior valor entre os n primeiros elementos do array a (n ≥ 1). A função main já está pronta e lê n (1 ≤ n ≤ 100) e n inteiros (valor absoluto até 10000)."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
n == 1), o máximo é a[0]. Caso contrário, retorne o maior entre "o máximo dos n−1 primeiros", array_max(a, n - 1), e o último elemento, a[n - 1].#include <stdio.h> int array_max(const int a[], int n) { if (n == 1) { return a[0]; } int m = array_max(a, n - 1); if (a[n - 1] > m) { return a[n - 1]; } return m; } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } printf("Máximo: %d\n", array_max(a, n)); return 0; }
a[n - 1], e não a[n] (a[n] está fora dos limites). Guardando o resultado da chamada recursiva na variável m, você não precisa escrever a mesma chamada duas vezes.int is_palindrome(const char s[], int left, int right), que retorna 1 se o trecho s[left]…s[right] da string s for um palíndromo (lido igual de frente para trás e de trás para frente) e 0 caso contrário. A função main já está pronta: ela lê uma string sem espaços, de letras minúsculas (1 a 100 caracteres), e testa a string inteira."Executar" roda seu código com a entrada acima. "Corrigir" testa com 6 entradas preparadas.
left >= right (sobrou 1 caractere ou nenhum), é palíndromo: retorne 1. Se as pontas s[left] e s[right] forem diferentes, retorne 0. Se forem iguais, faça o mesmo teste recursivamente na parte de dentro, (left + 1, right - 1), e retorne o resultado.#include <stdio.h> #include <string.h> int is_palindrome(const char s[], int left, int right) { if (left >= right) { return 1; } if (s[left] != s[right]) { return 0; } return is_palindrome(s, left + 1, right - 1); } int main(void) { char s[101]; scanf("%100s", s); int len = (int)strlen(s); if (is_palindrome(s, 0, len - 1)) { printf("%s é um palíndromo\n", s); } else { printf("%s não é um palíndromo\n", s); } return 0; }
is_palindrome(...) e esquecer o return, o resultado do teste interno não chega a quem chamou (usar esse valor é comportamento indefinido). Se a condição de parada for só left == right, em strings de tamanho par (como abba) left e right se cruzam e a leitura vai além dos limites da string.void hanoi(int n, char from, char to, char via), que mostra os passos para levar todos os discos para C (ela move n discos de from para to, usando via como pino auxiliar). A cada movimento, mostre uma linha "Disco k: X -> Y". A função main já está pronta: ela lê n (1 ≤ n ≤ 10) e chama hanoi(n, 'A', 'C', 'B')."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
n == 0, não faz nada.#include <stdio.h> void hanoi(int n, char from, char to, char via) { if (n == 0) { return; } hanoi(n - 1, from, via, to); printf("Disco %d: %c -> %c\n", n, from, to); hanoi(n - 1, via, to, from); } int main(void) { int n; scanf("%d", &n); hanoi(n, 'A', 'C', 'B'); return 0; }
int bsearch_rec(const int a[], int lo, int hi, int key), que procura key no trecho a[lo]…a[hi] de um array a em ordem crescente e retorna o índice se encontrar, ou −1 se não encontrar. A função main já está pronta e lê, nesta ordem, n (1 ≤ n ≤ 100), n inteiros em ordem estritamente crescente (sem valores repetidos) e o valor key a procurar. Os índices começam em 0."Executar" roda seu código com a entrada acima. "Corrigir" testa com 6 entradas preparadas.
lo > hi (o trecho de busca está vazio), retorne −1. Olhe o meio, mid = (lo + hi) / 2: se a[mid] == key, retorne mid; se key for menor, procure recursivamente na metade esquerda (lo, mid - 1); se for maior, na metade direita (mid + 1, hi), e dê return nesse resultado.#include <stdio.h> int bsearch_rec(const int a[], int lo, int hi, int key) { if (lo > hi) { return -1; } int mid = (lo + hi) / 2; if (a[mid] == key) { return mid; } else if (key < a[mid]) { return bsearch_rec(a, lo, mid - 1, key); } else { return bsearch_rec(a, mid + 1, hi, key); } } int main(void) { int a[100]; int n, key; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } scanf("%d", &key); int pos = bsearch_rec(a, 0, n - 1, key); if (pos >= 0) { printf("%d está em a[%d]\n", key, pos); } else { printf("%d não foi encontrado\n", key); } return 0; }
(lo, mid) ou (mid, hi), às vezes o trecho não diminui e a mesma chamada se repete sem parar. mid já foi examinado, então sempre o deixe de fora. Como o trecho cai pela metade a cada chamada, mesmo com 100 elementos a busca termina em cerca de 7 chamadas.int comb(int n, int r), que retorna o número de combinações nCr (formas de escolher r itens entre n), com recursão usando a relação nCr = n−1Cr−1 + n−1Cr (sem usar fatorial). Considere nC0 = nCn = 1. A função main já está pronta e lê n e r (0 ≤ r ≤ n ≤ 20)."Executar" roda seu código com a entrada acima. "Corrigir" testa com 6 entradas preparadas.
r == 0 || r == n, retorne 1. Caso contrário, return comb(n - 1, r - 1) + comb(n - 1, r); (no triângulo de Pascal, "a soma dos dois números logo acima").#include <stdio.h> int comb(int n, int r) { if (r == 0 || r == n) { return 1; } return comb(n - 1, r - 1) + comb(n - 1, r); } int main(void) { int n, r; scanf("%d %d", &n, &r); printf("%dC%d = %d\n", n, r, comb(n, r)); return 0; }
r == 0, comb(n - 1, r) gera chamadas em que r fica maior que n, e elas não param nem quando n fica negativo. São necessárias as duas pontas (r=0 e r=n). O método com fatorial, n!/(r!(n−r)!), facilmente estoura o int nos fatoriais intermediários (13! já passa do limite do int), então esta recursão também é mais segura nesse aspecto.void permute(int perm[], int used[], int depth, int n). perm é a permutação em construção, used[k] vale 1 se o número k+1 está em uso, e depth é quantos números já foram escolhidos. A função main já está pronta: ela lê n (1 ≤ n ≤ 5) e chama permute(perm, used, 0, n)."Executar" roda seu código com a entrada acima. "Corrigir" testa com 5 entradas preparadas.
depth == n, todos os números foram escolhidos: mostre perm e volte. Caso contrário, entre os números de 1 a n, escolha em ordem crescente cada um que ainda não foi usado, coloque-o em perm[depth], marque used com 1 e chame permute(perm, used, depth + 1, n). Ao voltar, coloque used de novo em 0.#include <stdio.h> void permute(int perm[], int used[], int depth, int n) { if (depth == n) { for (int i = 0; i < n; i++) { printf("%d ", perm[i]); } printf("\n"); return; } for (int k = 0; k < n; k++) { if (!used[k]) { used[k] = 1; perm[depth] = k + 1; permute(perm, used, depth + 1, n); used[k] = 0; } } } int main(void) { int perm[5]; int used[5] = {0}; int n; scanf("%d", &n); permute(perm, used, 0, n); return 0; }
used[k] = 0; depois de voltar da recursão, um número usado uma vez nunca mais pode ser escolhido, e só a primeira permutação aparece. O array é compartilhado com a função chamada, então você mesmo precisa controlar quando colocar e tirar a marca. Há n! permutações (120 para n=5).