[C] Stringa palindroma

[magix2003]

Ciao a tutti,
devo sviluppare in C una funzione che controlli se una stringa è palindroma usando la ricorsione. Sono arrivato ad un buon punto con questa funzione:

int isPalindrome(int i, int j) // i è 0(l'inizio della stringa) j è la lunghezza meno 1
{
if (j == 0)
{
return 1;
}else if (j == 1)
{
return 1;
}else
{
if (str[i] == str[j]){
return isPalindrome(i+1,j-1);
}else{
return 0;
}
}
}


Che compila e funziona correttamente. La mia domanda è se però l'idea di fondo è corretta. Riguardando mi sembra che faccia delle chiamate ricorsivi inutili. Secondo voi?
Grazie

[yorkeiser]

Mi sembra assolutamente corretta e per di più minimale, non puoi risparmiare altre ricorsioni. Al limite puoi accorpare le due condizioni j=0 e j=1 in un singolo OR, ma per il resto, decidendo di farla ricorsivamente, mi pare assolutamente buona.

[magix2003]

Ma, io adesso l'ho modificata in questo modo:


int isPalindrome(int i, int j)
{
if ((j-i) == 0) // <-----------
{
return 1;
}else if ((j-i) == 1) // <----------
{
return 1;
}else
{
if (str[i] == str[j]){
return isPalindrome(i+1,j-1);
}else{
return 0;
}
}
}



In questo modo, secondo me, controlla la reale lunghezza della stringa. O sbaglio?

[yorkeiser]

Dipende da cosa intendi per j. Se j è l'effettiva lunghezza della stringa, come hai scritto nel primo post, allora è giusto quello che hai postato all'inizio, escluso il fatto che effettivamente dovresti richiamare la riscorsione con isPalindrome(i+1,j-2), dal momento che avanzi di un carattere dall'inizio e ritorni indietro di 1 dalla fine (quindi la lunghezza della sottostringa diminuisce di 2). Se invece per j intendi la posizione dell'ultimo carattere all'interno della stringa iniziale, allora è corretto (ad occhio, senza controllare sui bound) il tuo secondo intervento

[magix2003]

Per chiarezza posto anche il main:

int main(){
int res;
res = isPalindrome(0,strlen(str)-1);
if (res == 1){
printf("The string is palindrome\n");
}else if (res == 0){
printf("The string is not palindrome\n");
}else{
printf("An error occured");
}
}


Siccome sia i che j non agiscono sulla stringa ma mantengono solo la posizione nella stringa secondo me la seconda via è quella giusta.
Comunque grazie mille per l'aiuto

[Qu@ker]

#include <stdio.h>
#include <string.h>

int isPalindrome(int i, int j, char *str)
{
if (i >= j)
return 1;
if (str[i] == str[j])
return isPalindrome(i+1, j-1, str);
return 0;
}

int main(void)
{
char *test[] = {"anna", "marianna", "saippuakivikauppias"};
int i;

for (i = 0; i < sizeof test/sizeof test[0]; ++i)
printf("\'%s\'%s e\' palindromo.\n", test[i],
isPalindrome(0, strlen(test[i])-1, test[i]) ? "" : " non");

return 0;
}

[magix2003]

#include <stdio.h>
#include <string.h>

int isPalindrome(int i, int j, char *str)
{
if (i >= j)
return 1;
if (str[i] == str[j])
return isPalindrome(i+1, j-1, str);
return 0;
}

int main(void)
{
char *test[] = {"anna", "marianna", "saippuakivikauppias"};
int i;

for (i = 0; i < sizeof test/sizeof test[0]; ++i)
printf("\'%s\'%s e\' palindromo.\n", test[i],
isPalindrome(0, strlen(test[i])-1, test[i]) ? "" : " non");

return 0;
}


Grazie per la risposta. Il tuo codice è sicuramente più completo e raffinato rispetto al mio, però io volevo sapere se il mio codice è corretto o se c'è qualcosa che non va. Grazie comunque...

[cionci]

Ma, io adesso l'ho modificata in questo modo:


int isPalindrome(int i, int j)
{
if ((j-i) == 0) // <-----------
{
return 1;
}else if ((j-i) == 1) // <----------
{
return 1;
}else
{
if (str[i] == str[j]){
return isPalindrome(i+1,j-1);
}else{
return 0;
}
}
}



In questo modo, secondo me, controlla la reale lunghezza della stringa. O sbaglio?
str la dovresti passare alla funzione...le variabili globali non sono buona cosa ;)
Ti potrebbe venire segnalato che manca un return per un path del codice...anche se in realtà c'è...
Gli else sono inutili in tutti e tre i casi...tra l'altro i primi due if possono essere raggruppati...

[magix2003]

str la dovresti passare alla funzione...le variabili globali non sono buona cosa ;)
Ti potrebbe venire segnalato che manca un return per un path del codice...anche se in realtà c'è...
Gli else sono inutili in tutti e tre i casi...tra l'altro i primi due if possono essere raggruppati...

Grazie per le dritte... Però ho trovato un'altro "baco" dell'argoritmo. Se imposto il valore di char a[] è impostato a "" cioè la stringa vuota, l'algoritmo non funziona. Questo perché ho scoperto che la lunghezza è 0 se la stringa è vuota, quindi il carattere /0 di chiusura della stringa non viene appeso. Per non avere questo problema l'unico metodo per risolvere è fare un ciclo if prima della chiamata della funzione oppure esiste un altro modo?
Grazie