(Recursividade) Escreva uma função recursiva que produza o reverso de um string, reverse(char s[])
Passo 1
Beleza, vamos resolver esse exercício que pede para a gente escrever uma função recursiva que inverta uma string. Esse assunto faz parte de Recursividade, uma técnica de programação onde a função chama a si mesma para resolver partes menores do problema. Para resolver isso, vamos precisar entender como as funções recursivas funcionam e como manipular strings na linguagem que estiver usando.
Passo 2
Primeiro, vamos entender o que é recursividade. Uma função recursiva é aquela que se chama novamente para resolver um problema menor até chegar a um caso que ela já sabe resolver diretamente, chamado de caso base. Então, para inverter uma string de forma recursiva, precisamos definir esse caso base e como a função vai se chamar para inverter partes menores da string.
Passo 3
Agora, pense na string que queremos inverter. A ideia é pegar o primeiro caractere, inverter o restante da string e depois colocar o primeiro caractere no final. Por exemplo, se tivermos a string “abc”:
- Pegamos “a” e queremos inverter “bc”.
- Para inverter “bc”, pegamos “b” e invertemos “c”.
- “c” é o caso base, pois é uma string de um caractere, então ela mesma é o inverso.
- Voltando, colocamos “b” após “c”, formando “cb”.
- Finalmente, colocamos “a” após “cb”, resultando em “cba”.
Passo 4
Vamos traduzir essa lógica para uma função. Vamos escrever em C como exemplo:
#include <stdio.h>
#include <string.h>
// Função recursiva para inverter uma string
void reverse(char s[]) {
int length = strlen(s);
if (length <= 1) {
return;
}
// Troca o primeiro caractere com o último
char temp = s[0];
s[0] = s[length - 1];
s[length - 1] = temp;
// Cria uma substring sem o primeiro e o último caractere
char substring[length - 1];
strncpy(substring, s + 1, length - 2);
substring[length - 2] = '\0';
// Chama a função recursivamente na substring
reverse(substring);
// Coloca a substring invertida de volta na string original
strncpy(s + 1, substring, length - 2);
}
Resposta
A função recursiva para inverter uma string fica assim:
#include <stdio.h>
#include <string.h>
// Função recursiva para inverter uma string
void reverse(char s[]) {
int length = strlen(s);
if (length <= 1) {
return;
}
// Troca o primeiro caractere com o último
char temp = s[0];
s[0] = s[length - 1];
s[length - 1] = temp;
// Cria uma substring sem o primeiro e o último caractere
char substring[length - 1];
strncpy(substring, s + 1, length - 2);
substring[length - 2] = '\0';
// Chama a função recursivamente na substring
reverse(substring);
// Coloca a substring invertida de volta na string original
strncpy(s + 1, substring, length - 2);
}
Exercícios relacionados
(String) Escreva um programa que mostre uma string na tela pela ordem em que está escrita e pela ordem contrária. DEVE usar apenas apontador para percorrer as strings.
Leia um número N inteiro. Calcule sua raiz INTEIRA. Exemplo:
, raiz inteira
.
(Matriz) Escreva um programa que armazene 9 valores para uma matriz
gerados aleatoriamente, os valores devem ser menores que 100. (1) Calcule a soma dos elementos (2) Retorne a quantidade acima do valor 50 .
A função rand() devolve um número entre os limites mencionados.
A função rand() parte da mesma semente para realizar o cálculo dos números aleatórios.
Para variar a semente, é usado um valor gerado através do relógio do computador.
A função rand() devolve um número entre os limites mencionados.
A função rand() parte da mesma semente para realizar o cálculo dos números aleatórios.
Para variar a semente, é usado um valor gerado através do relógio do computador.
Apresente um esquema recursivo para dividir dois números inteiros usando contagens sucessivas. Por exemplo: calcular A/B sendo
e
. Sabemos que dividir A por B é o mesmo que descobrir quantas vezes B cabe em A . Assim, para dividir 18 por 4 podemos contar o no. de vezes que 4 cabe dentro de 18 .