[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]

Originariamente inviato da 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;
}

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]

Originariamente inviato da 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?

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]

Originariamente inviato da cionci

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