Ancora (e ancora e ancora, ricorsivamente...) ricorsione

di
enricoscarsissimo
il
4 risposte
E
enricoscarsissimo
Utente Attivo
Iscritto da
dic, 2018
Messaggi:
79

Ancora (e ancora e ancora, ricorsivamente...) ricorsione

Buongiorno a tutti. Vi propongo un altro esercizio sulla ricorsione, anche stavolta mi sembra proprio di perdermi un passaggio perchè non riesco proprio a capire come non torni.
Testo: Si definisca una funzione … ugualioquasi( … ) che confronta due stringhe e restituisce 1 se sono uguali o ottenibili
l’una dall’altra con un solo scambio di due caratteri consecutivi, 0 se invece sono significativamente diverse. Se
formulata in modo ricorsivo vale un punto “extra”. [4(+1) p.] 
int ugualioquasi(char *v1,char *v2){
	if(strlen(v1)!=strlen(v2))				//condizione che si può verificare solo all'avvio, alle successive iterazioni non può avvenire
		return 0;						//(facendo scorrere i puntatori contemporaneamente)
	else if(strcmp(v1,v2)==0)		//se le stringhe (o le sottostringhe alle iterazioni successive) sono uguali ritorna 1
		return 1;
	else if (v1[0]==v2[0])			//se non sono uguali ma il primo elemento lo è richiama con il puntatore all'elem seguente
		 ugualioquasi(v1+1,v2+1);
	if(v1[0]!=v2[0] && v1[0]==v2[1] && v1[1]==v2[0])		//se non sono uguali neanche i primi 2 elementi, verifica che lo siano rispetto a quello
		 ugualioquasi(v1+2,v2+2);						//successivo dell'altro vettore. Se così è, salta un elemento
	else return 0;
Le parole che uso come test e che prontamente restituiscono 0 sono "trono" e "torno".
Grazie in anticipo dell'eventuale aiuto

4 Risposte

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Ancora (e ancora e ancora, ricorsivamente...) ricorsione

    Sinceramente non capisco perchè una versione ricorsiva debba essere ritenuta a prescindere la scelta migliore tanto da assegnare un punto extra! Di solito la versione ricorsiva di un algoritmo è meno performante di quella iterativa, ma potenzialmente più semplice; ci tengo però a sottolineare che non esiste una regola di carattere generale e che la scelta va ponderata volta per volta trovando il giusto compromesso tra prestazioni e semplicità! Nel caso specifico per esempio mi sembra molto più "naturale" un approccio di tipo iterativo.

    Tornando al codice, sinceramente non ho capito fino in fondo quale siano le tue intenzioni e non ho molta voglia di analizzare il codice per comprendere ciò che effettivamente avviene. Il mio consiglio quindi è quello di implementare un algoritmo di tipo iterativo e a quel punto, se è il caso, possiamo ragionare su come convertirlo in ricorsivo.

    P.S.
    Preferivo la vecchia skin del forum!
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Ancora (e ancora e ancora, ricorsivamente...) ricorsione

    Ho aggiunto dei commenti sperando sia più comprensibile l'idea alla base. La cosa strana è che stampando a inizio programma il valore di strcmp(v1,v2) mi dice che alla fine v1 e v2 sono uguali, nonostante poi non ritorni 1.
    Comunque sono d'accordo che la versione iterativa fosse molto più semplice, era più che altro per esercitarmi
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Ancora (e ancora e ancora, ricorsivamente...) ricorsione

    Vabbè se non vuoi seguire il mio consiglio

    Nippolo ha scritto:

    Il mio consiglio quindi è quello di implementare un algoritmo di tipo iterativo e a quel punto, se è il caso, possiamo ragionare su come convertirlo in ricorsivo.

    ragioniamo pure sulla strada che hai deciso di intraprendere:
    - innanzitutto quelle chiamate ricorsive sono del tutto inutili se non le fai precedere da un return;
    - aggiungendo i return il programma "sembra" funzionare con le stringhe trono e torno, ma ritorna 1 anche con le stringhe abcasta e acbatsa... c'è quindi altro che non va!
    - come si deduce anche dai tuoi commenti, non ha alcun senso calcolare la lunghezza delle stringhe nelle chiamate ricorsive successive alla prima.

    In ogni caso il tuo codice anche una volta aggiustato sarà cmq poco performante, infatti con le funzioni strlen() e strcmp() andrai a scorrere le due stringhe molte volte, quando invece basta scorrerle 1 volta sola (o anche meno). La mia idea è la seguente: 
    #include <stdio.h>

int main()
{
    char s1[] = "treno";
    char s2[] = "terno";
    unsigned int v[3];
    unsigned int i = 0;
    unsigned int j = 0;
    while(s1[i] && s2[i] && j < 3)
    {
        if(s1[i] != s2[i])
        {
            v[j++] = i;
        }
        ++i;
    }
    printf("%d", (s1[i] == s2[i] && (!j || (j == 2 && s1[v[0]] == s2[v[1]] && s1[v[1]] == s2[v[0]] && v[1] - v[0] == 1))));
}
    A questo punto se proprio vuoi implementare una versione ricorsiva avrebbe molto più senso rifarsi a questo codice o cmq a qualcosa di simile.

    EDIT:
    Corretta una cosa nel codice.
  • E
    enricoscarsissimo
    Utente Attivo
    Iscritto da
    dic, 2018
    Messaggi:
    79

    Re: Ancora (e ancora e ancora, ricorsivamente...) ricorsione

    Nel mio strano mondo ero convinto che se invocavo senza return quando poi effettivamente lo mettevo lo ritornavo direttamente al main e non al chiamante, invece lo ritornavo si ma senza usarlo in nessun modo, lol. Riparto da qui, thanks.
Devi accedere o registrarti per scrivere nel forum
4 risposte