Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Problema con funzioni ricorsive
Forum - C/C++ - Problema con funzioni ricorsive

Avatar
gabrieleoliaro (Normal User)
Newbie


Messaggi: 3
Iscritto: 04/07/2013

Segnala al moderatore
Postato alle 19:39
Giovedì, 04/07/2013
Ciao a tutti. Studiando il C++ mi sono imbattuto ieri in questo codice:

Codice sorgente - presumibilmente C++

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void visualizzaVettore(int v[], int n)
  5. {
  6.      if (n < 0)
  7.         return;
  8.      visualizzaVettore(v, n-1);
  9.      cout<<v[n]<<endl;
  10. }
  11.  
  12. int main()
  13. {
  14.     int v [15] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
  15.     visualizzaVettore(v, 14);
  16.     system("pause");
  17.     return 0;
  18. }



E' un (apparentemente) semplicissimo programma che permette di visualizzare sullo schermo gli elementi di un vettore v (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15). Però non riesco a capire come funzioni: la ricorsione dovrebbe non permettere l'esecuzione del cout, dato che è scritta prima!

Qualcuno mi può spiegare come mai mostra i valori in ordine crescente, da 1 a 15???

Grazie


PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 413
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 22:56
Giovedì, 04/07/2013
Dici bene, il cout è dopo la chiamata ricorsiva... però, nota due cose: il parametro n è inizialmente 14, cioè la lunghezza dell'array - 1, e nelle chiamate ricorsive decresce(n-1);
inoltre la condizione di uscita dalla ricorsione è n < 0, cioè quando si è andati oltre il primo elemento.

Questo dovrebbe farti intuire che l'array viene percorso al contrario, quindi si arriva al massimo livello di nesting per stampare il primo elemento, e dopo si torna indietro fino a stampare l'ultimo.

Se non sei ancora convinto, si può dimostrare che il codice funziona:
infatti, senza andare nel formalismo per cui sarebbe necessaria l'induzione, puoi fare un ragionamento del genere:

visualizzaVettore(int v[], int n) stampa il vettore v
Per poter utilizzare la ricorsione non si fa altro che scomporre questa operazione in
* stampa il vettore v fino al penultimo elemento
* stampa l'ultimo elemento

Ma per stampare il vettore v fino al penultimo elemento, posso ancora usare visualizzaVettore, solo che faccio decrescere i'indice.

Dopodichè, sapendo che nel caso base il nostro codice funziona ancora(se il vettore è di lunghezza zero, e cioè n = 0, allora visualizzaVettore non stampa niente), possiamo dedurre che il codice è valido per ogni n.

Dimmi se sono stato chiaro.




PM Quote
Avatar
gabrieleoliaro (Normal User)
Newbie


Messaggi: 3
Iscritto: 04/07/2013

Segnala al moderatore
Postato alle 23:13
Giovedì, 04/07/2013
Ma quindi il programma si ricorda la "cronologia" dei valor di n e poi li scrive in ordine crescente, giusto??

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 413
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 23:27
Giovedì, 04/07/2013
Testo quotato

Postato originariamente da gabrieleoliaro:

Ma quindi il programma si ricorda la "cronologia" dei valor di n e poi li scrive in ordine crescente, giusto??


Non proprio ma una cosa del genere... ti faccio l'esempio di esecuzione con un array di tre elementi(non è codice C):

visualizzaVettore([1,2,3], 2)
   2 < 0 è falso ,quindi si continua
   visualizzaVettore([1,2,3], 1)
       1 < 0 è falso, quindi si continua
           visualizzaVettore([1,2,3], 0)
           0 < 0 è falso, quindi continua
                visualizzaVettore([1,2,3], -1)
                    -1 < 0 è vero, quindi si termina la funzione corrente;
                              ora l'esecuzione riparte da dov'era stata interrotta
                               l'ultima volta, cioè dalla funzione con n = 0
           cout << v[0] << endl;  // stampa il primo elemento
           la funzione termina, quindi si riparte dall'ultimo punto di interruzione, cioè da n = 1
       cout << v[1] << endl; // stampa il secondo elemento
    la funzione termina e l'esecuzione riparte da dov'era stata interrotta, cioè da n = 2
    cout << v[2]  << endl; // stampa il terzo ed ultimo elemento
    la funzione termina e si ritorna al punto dove era stata chiamata, in questo caso dal main()


Segui l'esecuzione attentamente e guarda il modo in cui ho indentato le chiamate, allineando il codice di una stessa chiamata ricorsiva sullo stesso livello.

A livello più basso, quello che succede è che la CPU, quando una funzione effettua una chiamata ad un'altra funzione(ricorsiva o meno), salva lo stato dove si era interrotta l'esecuzione nel cosidetto stack, esegue la funzione chiamata, e quando questa ha terminato guarda lo stack per sapere da dove riprendere l'esecuzione.

Più avanti studierai che lo stack è una struttura dati che ha questo comportamento: le cose che si aggiungono allo stack, con un'operazione detta "push" vanno in cima allo stack, e l'operazione che toglie dallo stack toglie l'elemento in cima, con un'operazione detta "pop".

Ti può aiutare il fatto che in italiano stack significa "pila", infatti puoi pensare ad esempio ad una pila di libri: per aggiungerne uno lo metti sopra alla pila, e per toglierlo prendi quello in cima e lo togli.

Cosa c'entra questo con le chiamate ricorsive? Se hai guardato bene il comportamento della funzione, avrai capito che lo stato dell'esecuzione viene salvato attraverso un "push" e ripristinato attraverso un "pop".
Per questo motivo la funzione parte da n-1, arriva a 0, e dopo va all'indietro: tutti gli stati vengono mano a mano "pushati" sullo stack, e quando si arriva in fondo (n=-1) si comincia a risalire con il "pop" e quindi si stampano gli elementi nell'ordine corretto.        
  

  



PM Quote
Avatar
gabrieleoliaro (Normal User)
Newbie


Messaggi: 3
Iscritto: 04/07/2013

Segnala al moderatore
Postato alle 23:35
Giovedì, 04/07/2013
Grazie mille, ora è tutti chiaro!

PM Quote