Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Ciao a tutti. Studiando il C++ mi sono imbattuto ieri in questo codice:
Codice sorgente - presumibilmente C++
#include <iostream>
usingnamespace std;
void visualizzaVettore(int v[], int n)
{
if(n < 0)
return;
visualizzaVettore(v, n-1);
cout<<v[n]<<endl;
}
int main()
{
int v [15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
visualizzaVettore(v, 14);
system("pause");
return0;
}
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???
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.
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.
