[C++] Sottolista

[progrina]

Buonasera a tutti..ho alcuni problemi con il seguente esercizio.
In pratica, sono riuscita a fare la versione iterativa ma non riesco a fare una versione ricorsiva che non mi dia problemi..Vi posto il testo :

Progettare un algoritmo ricorsivo sottoforma di function che date due linked list head1 e head2 (con campo info di tipo integer), restituisca TRUE se head2 è sottolista di head1, FALSE altrimenti.
Ad es. se in input si ha
head1= 2 -> 0 -> 10 -> 1 -> 21 -> 11
head2= 0 -> 10 -> 1
la function ritorna TRUE.
Altrimenti se:
head1= 2 -> 0 -> 10 -> 1 -> 21 -> 11
head2= 0 -> 1 -> 21
la function ritorna FALSE.

Ho fatto tante prove una delle quali è la seguente. Il punto è che durante l'esecuzione il programma mi salta le chiamate alla funzione ricorsiva.

bool sottolista(list *head1,list *head2){
     if(head1->info != head2->info)
        sottolista(head1->next,head2);
     if(head1 != NULL && head2 != NULL){
      if(head1 -> info == head2 ->info)
        sottolista(head1->info,head2->info);
      else return false;}
     if(head2 == NULL) return true;
}

Spero possiate aiutarmi, grazie a tutti!

[ramy89]

Gli if dove verifichi se non ci sono puntatori a NULL devono stare per primi.
Altrimenti accedi ai campi anche se c'è un puntatore a NULL, causando segmentation fault.

[progrina]

Non me n'ero accorta ma c'è un errore di distrazione nel codice precedente!
Comunque grazie per la risposta ramy89..ho corretto il codice in questo modo:

bool sottolista(list *head1,list *head2){
     if(head1 != NULL && head2 != NULL){
       if(head1->info != head2->info)
        sottolista(head1->next,head2);
     else 
        sottolista(head1->next,head2->next);
     }
     if(head2 == NULL) return true;
     else return false;
}

Il punto è che così la funzione mi ritorna sempre vera, perchè la funzione mi trova sempre (attendendomi all'esempio che ho scritto sopra) che i 3 elementi di head2 sono presenti in head1 anche se non consecutivamente.
Per ovviare a questo problema devo introdurre un altra variabile?

[ramy89]

Se gli elementi sono diversi devi ritornare false.
Poi sta eseguendo la sottolista senza prenderne il risultato.
Modificala così:

bool sottolista(list *head1,list *head2){
     if(head1 != NULL && head2 != NULL){
       if(head1->info != head2->info)
        return false;  // perchè chiamare ricorsivamente la sottolista?
     else                           // il confronto ha avuto esito negativo
        return sottolista(head1->next,head2->next);
     }
     if(head2 == NULL) return true;
     else return false;
}