Usando recursividade para determinar se uma palavra é um palíndromo

Um palíndromo é uma palavra que é soletrada do mesmo jeito de trás para frente. Por exemplo, rotor é palíndromo, mas motor não.

Como você pode usar recursividade para determinar se uma palavra é um palíndromo? Vamos começar entendendo o que é um caso base. Considere a palavra a. Ela é um palíndromo. De fato, não temos que pensar em palíndromos como palavras reais em português (ou qualquer outra língua que você quiser usar). Podemos pensar em um palíndromo simplesmente como uma sequência de letras que é lida do mesmo jeito de trás para frente, como xyzyzyx. Chamamos uma sequência de letras de string. Então, podemos dizer que qualquer string que contenha apenas uma letra é, por padrão, um palíndromo. Uma string pode não conter nenhuma letra; chamamos uma string sem nenhuma letra de string vazia. Uma string vazia também pode ser um palíndromo, já que é "lida" do mesmo jeito de trás para frente. Então, vamos dizer que qualquer string que contenha no máximo uma letra é um palíndromo. Esse é nosso caso base: uma string com nenhuma ou uma letra é um palíndromo.

E se a string tiver duas ou mais letras? É aqui que vamos usar nosso caso recursivo. Considere o palíndromo rotor. A primeira e a última letras são iguais, e isso deve ser verdade para todos os palíndromos. Por outro lado, se a primeira e última letras não forem iguais, como em motor, então não é possível que a string seja um palíndromo. Então, temos um modo de declarar que uma string não é um palíndromo: quando a primeira e a última letras são diferentes. Podemos pensar nessa situação como outro caso base, já que temos a resposta imediatamente. Voltando a quando a primeira e a última letras são iguais, o que isso nos diz? A string pode ser um palíndromo. Mas também pode não ser. Na string amora, a primeira e a última letra são iguais, mas a string não é um palíndromo. Suponha que tiremos a primeira e a última letras, deixando a string mor. Nesse caso, a primeira e a última letras não são iguais, e então sabemos que amora não é um palíndromo.

Então, é assim que podemos usar a recursividade para determinar se uma string é um palíndromo. Se a primeira e a última letras forem diferentes, então declare que a string não é um palíndromo. Caso contrário, remova a primeira e última letras e determine se a string que permanece — o subproblema — é um palíndromo. Declare que a resposta da string mais curta é a resposta para a string original. Quando você chegar a uma string sem letras, ou com apenas uma letra, declare que ela é um palíndromo. Aqui está uma visualização disso para duas palavras que discutimos:

Como descreveríamos isso em pseudocódigo?

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.