Usar recursividad para determinar si una palabra es un palíndromo o no

Un palíndromo es una palabra que se escribe igual al derecho y al revés. Por ejemplo, rotor es un palíndromo, pero motor no.

¿Cómo puedes usar recursividad para determinar si una palabra es un palíndromo? Vamos a empezar por entender qué es un caso base. Consideremos la palabra a. Es un palíndromo. De hecho, no tenemos que pensar en palíndromos como palabras reales en el idioma español (o cualquier idioma que desees considerar). Podemos pensar en un palíndromo como cualquier secuencia de letras que se lee igual hacia adelante y hacia atrás, como xyzyzyx. A una secuencia de letras la llamamos una cadena. Entonces podemos decir que cualquier cadena que contenga una sola letra es, por defecto, un palíndromo. Ahora, una cadena puede no contener ninguna letra; a una cadena de cero letras la llamamos una cadena vacía. Una cadena vacía también es un palíndromo, ya que se "lee" del mismo modo hacia adelante y hacia atrás. Así que ahora digamos que cualquier cadena que contenga a lo más una letra es un palíndromo. Ese es nuestro caso base: una cadena con exactamente cero letras o una letra es un palíndromo.

¿Qué pasa si la cadena contiene dos o más letras? Aquí es en donde tendremos nuestro caso recursivo. Considera el palíndromo rotor. Su primera y su última letra son la misma, y esta característica debe cumplirse para cualquier palíndromo. Por otro lado, si la primera y la última letra no son iguales, como en motor, entonces la cadena no puede ser un palíndromo. Así que ahora tenemos una manera de afirmar que una cadena no es un palíndromo: cuando su primera y su última letra son diferentes. Podemos pensar acerca de esta situación como otro caso base, puesto que tenemos la respuesta inmediatamente. De regreso a cuando la primera y la última letra son la misma, ¿qué nos dice eso? La cadena puede ser un palíndromo. Pero también, puede no serlo. En la cadena rotar, la primera y última letra son la misma, pero la cadena no es un palíndromo. Supón que desechamos la primera y la última letra, dejando la cadena ota. Entonces la primera y la última letra de esta cadena restante no son la misma, entonces sabemos que rotar no es un palíndromo.

Así que aquí está cómo podemos determinar de manera recursiva si una cadena es un palíndromo. Si la primera y la última letra difieren, entonces afirma que la cadena no es un palíndromo. De lo contrario, desecha la primera y la última letra y determina si la cadena que queda (el subproblema) es un palíndromo. Afirma que la respuesta para la cadena más corta es la respuesta para la cadena original. Una vez que llegues a una cadena sin letras o con una sola letra, afirma que es un palíndromo. Aquí está una visualización de eso para las dos palabras que discutimos:

¿Cómo describiríamos eso en pseudocódigo?

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.