Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 6: Algoritmos recursivos- Recursividad
- La función factorial
- Desafío: factorial iterativo
- Factorial recursivo
- Desafío: factorial recursivo
- Propiedades de los algoritmos recursivos
- Usar recursividad para determinar si una palabra es un palíndromo o no
- Desafío: ¿una cadena de caracteres es un palíndromo?
- Calcular potencias de un número
- Desafío: potencias recursivas
- Recursividad múltiple con el triángulo de Sierpinski
- Mejorar la eficiencia de las funciones recursivas
- Proyecto: arte recursivo
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
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?
- Si la cadena está hecha de cero letras o de una letra, entonces es un palíndromo.
- De lo contrario, compara la primera y la última letra de la cadena.
- Si la primera y la última letra difieren, entonces la cadena no es un palíndromo.
- De lo contrario, la primera y la última letra son la misma. Elimínalas de la cadena y determina si la cadena que queda es un palíndromo. Toma la respuesta para esta cadena más pequeña y úsala como la respuesta para la cadena original.
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.
¿Quieres unirte a la conversación?
- Listo, este fue mas rápido. ¿A alguien le salió otra cosa?
var isPalindrome = function(str) {
// base case #1
if (str.length <= 1){
return true;
}
// base case #2
if (firstCharacter(str) !== lastCharacter(str)){
return false;
}
// recursive case
if (firstCharacter(str) === lastCharacter(str)){
return isPalindrome(middleCharacters(str));
}
};(3 votos) - cual es la función principal palíndromo(2 votos)
- Como agrego dos revisiones a este desafio?
checkPalindrome("a");
Program.assertEqual(isPalindrome("a"), true);
checkPalindrome("motor");
Program.assertEqual(isPalindrome("motor"), false);
checkPalindrome("rotor");
Program.assertEqual(isPalindrome("rotor"), true);(2 votos) - un palíndromo se podria decir que es una letra, se puede indentificar hacia delante como atras disminuyendo las letras en este teoria(1 voto)
- algoritmo para determinar la cantidad
de palabras palindromas(1 voto) - hola alguien me ayuda con el siguiente desafio?(1 voto)
- Querrás decir palíndromo.
Es una palabra que se lee igual de izquierda a derecha que de derecha a izquierda.(1 voto)