L'algoritmo di risoluzione del secondo esercizio è ok e dovrebbe funzionare. Quindi se puoi spiegarti meglio quando scrivi "cosi' ma non va" per capire se hai un errore a tempo di esecuzione, o un errore logico a monte.
Ora partendo dal secondo esercizio, immediatamente puoi notare che nel terzo esercizio all'interno della funzione pal, non esiste nessuna chiamata ricorsiva e che quindi quella funzione non può essere ricorsiva (la conferma la hai dal fatto che stai utilizzando un while che itera su tutta la stringa.
Ritorniamo a ragionare sui tre casi che ti ho postato ieri e ti riscrivo quì sotto per comodità e cerchiamo di trovarli all'interno della funzione che hai scritto tu:
- la stringa vuota è palindroma
- la stringa con un solo carattere è palindroma
- la stringa x y z è palindroma, se y è una stringa palindroma e x e z sono due caratteri uguali
In particolare la condizione 1 ci suggerisce un caso base del tipo "se la stringa è vuota allora è palindroma -> se s.length == 0 allora return true; la condizione 2 ci suggerisce un'estensione del caso base del tipo "se la stringa ha un solo carattere allora è palindroma -> se s.length <= 1 allora return true; quindi possiamo mettere insieme le due condizioni in un unico caso base con la condizione più restrittiva che è s.length <= 1;
Ora il terzo caso proviamo a riscriverlo in questi termini " una stringa è palindroma, se una sua sottostringa (in particolare quella "interna" privata di primo e ultimo carattere) è palindroma e due suoi elementi rispettano una particolare condizione". Come puoi vedere sto affermando che una stringa è palindroma se una sua parte più piccola è anche essa palindroma il che dovrebbe suggerirti di utilizzare la ricorsione.
Quindi il caso 1 e 2 possiamo riassumerli in questa istruzione condizionale
Codice:
IF (s.length() <= 1)
ris = true;
Mentre il caso 3 dobbiamo per forza (vista la natura della ricorsione) inserirli nel momento in cui il caso 1 e il caso 2 non si verificano
Codice:
ELSE
ris = (s[0] == s[s.length()-1] && palindroma(s.substring(1,s.length()-1));
in questo pseudo-codice con s.substring indico una funzione che ti ritorna una sottostringa compresa tra due indici che in questo caso sono il secondo carattere (indice 1) e penultimo carattere (indice s.length()-1), devi trovare il tuo equivalente su C++.
In questa situazione puoi notare come nel caso in cui non verifichiamo i due casi base (stringa vuota o con un solo carattere), andiamo prima a confrontare primo e ultimo carattere e poi chiamiamo la stessa funzione ma su una stringa più piccola. In questo modo hai la ricorsione.
Per allungare ancora di più il brodo ti illustro alcuni casi per farti capire il funzionamento dell'algoritmo con alcuni valori di input della stringa s:
caso 1: s = "c" la stringa c è palindroma perchè quando chiami la funzione pal(s) entriamo nell'IF poichè siamo nel caso 2 (stringa con 1 elemento) e quindi ritorna true.
caso 2: s = "ciao" la stringa c non è palindroma perchè quando chiami la funzione pal(s) non ti trovi nei casi base (1 e 2) e quindi viene eseguito il corpo dell'ELSE. In particolare avrai "c" == "o" e quindi l'AND all'interno dell'ELSE ritornerà false senza dover chiamare la funzione sulla sottostringa "ia".
caso 3: s = "ciac" la stringa c non è palindroma perchè quando chiami la funzione pal(s) non ti trovi nei casi base (1 e 2) e quindi viene eseguito il corpo dell'ELSE. In particolare avrai "c" == "c" e quindi la seconda parte dell'AND viene eseguita e in questo caso verrà chiamata la funzione sulla sottostringa "ia" che ritornerà false in quanto vale il discorso fatto nel caso 2 sopra illustrato.
caso 4: s = "ciic" la stringa è palindroma perchè alla prima esecuzione avrai la situazione illustrata nel caso 3, alla seconda esecuzione avrai la situazione illustrata nel caso 3 in particolare con la sottostringa "ii", e nella terza esecuzione avrai la situazione di stringa vuota che quindi ritorna true.
Spero di essere stato esaustivo e chiaro.
