Saber si es palíndromo o no, de forma recursiva

Hace unos días me pidieron por correo un programa que nos dijera si un string es palíndromo o no, pero usando una función recursiva. Me pareció interesante aunque raro que pidieran hacerlo de forma recursiva.

Tal vez recuerden que ya había publicado aquí una forma de saber si un string es palíndromo o no, el cual he descubierto (ahora que hice este otro) que no es muy eficiente.

Bueno pues el código es este:

#include
#include
using namespace std;
char cadenaf[50]={0}; int len, n=0;

string chk4palindrosity(int c)
{
    if(cadenaf[c] == cadenaf[len-1-c])
    {
        n++;
        if(n == len/2)
            return "Si es palindromo!";
        return chk4palindrosity(c+1);
    }
    else
        return "No es palindromo";
}

int main()
{
    char cadena[50],*parte;
    cout<<"Introduce un palindromo: "; cin.getline(cadena,50,'n');

    parte = strtok(cadena," ");                 //
    strcat(cadenaf,parte);                     //
    while((parte = strtok(NULL," ")) != NULL) //
        strcat(cadenaf,parte);               // quitar espacios del string

    len = strlen(cadenaf);
    cout << chk4palindrosity(0);
    cin.get();
}

La verdad es que es la función es recursiva de puro milagro. Lo que hice fue transformar el ciclo que checaba que los caracteres fueran iguales en una función en la que se aumenta una variable cada vez que se llama a sí misma.

El código ahora es más eficiente por dos simples razones:

  1. Se detiene y da el resultado a la primera comparación de caracteres que no sean iguales. Si el primer y el último caracter no son iguales, no es palíndromo y ya no sigue analizando los demás.
  2. Sólo checa la mitad de los caracteres. Si la mitad de los caracteres corresponden a la configuración de un palíndromo, ya no hay porqué seguir analizando la otra mitad.

Tal vez una mejor manera de hacerlo sería con una función que recibiera el string a analizar, comparar el primer y último caracter: si no, no es; si si, eliminar el primer y último caracter y volver a llamar a la función. Esto hasta que el numero de comparaciones ciertas sea igual a la mitad de la longitud inicial del string. ¿Alguien se anima a hacerlo?

3 thoughts on “Saber si es palíndromo o no, de forma recursiva

  1. Pues Yo lo he hecho comparando la primera con la ultima de forma recursiva, con el tipo de dato String y elimino los espacios sin usar funciones externas a la libreria iostream, de modo que funciona con el palindromo mas grande (sin acentos), ya que por ser de tipo “string” la memoria de la cadena es reservada de acuerdo al tamaño necesario, (no es necesario eso de char cadena[50]): me gustaria que me cites en tu web y lo publiques aca te lo dejo:

    http://pastebin.com/ziTKkAG8

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s