[C] Ricorsione

[ste9206]

Ciao a tutti. Non riesco a capire bene come funziona una funzione ricorsiva e come implementarla. Un esempio di codice ricorsivo:

long fact(int n)
{
	if(n == 0)
		return(1);
	else
		return(n * fact(n-1));
}

Oltretutto questo è uno degli esempi più semplici, ci sono anche chiamate ricorsive all'interno di cicli while/for che non ho la minima idea di come funzionino

Qualcuno mi riesce a spiegare bene come funziona questo tipo di funzioni, magari anche con qualche esempio diverso da questo? Grazie

[Alex'87]

Non c'è nulla di astruso, una funzione ricorsiva è una normale funzione che chiama se stessa... Cosa non ti è chiaro?

[oregon]

Fra l'altro ... ti è chiaro il flusso che un programma segue quando una funzione viene chiamata? Hai chiaro il concetto di stack?

[ste9206]

noi l'abbiamo vista sotto forma di albero binario. Tuttavia non riesco a capire la discesa ricorsiva, e i vari return una volta che si è giunti alla condizione di terminazione.

[oregon]

Cosa c'entra l'albero?

Parlavo del concetto di stack usato per memorizzare il punto di rientro delle funzioni.

[ste9206]

Ah, no quello non l'abbiamo mai fatto.

[MItaly]

http://it.wikipedia.org/wiki/Call_stack
Dopo aver capito cos'è lo stack la ricorsione dovrebbe essere relativamente più semplice da "immaginare" (anche se di per sé è un concetto astratto, lo stack è solo un dettaglio implementativo).

[ste9206]

Ok ho visto lo stack, tuttavia continuo a non avere chiaro come opera..

[Krahos]

Su questo argomento ho sbattuto la testa anch'io per un bel po' di tempo qualche mese fa prima di riuscire a capirlo. Vediamo se riesco a darti una mano. Nell'esempio da te postato devi immaginare una sequenza di funzioni che operano su un numero via via minore fino a 0. Immagina che l'input in questione sia 2 (giusto per prendere un numero ragionevolmente piccolo ma che spero sia sufficiente a capire) e osserva cosa fa la funzione.

1: la prima chiamata è fact (2). 2 non è zero quindi salta l'if e tenta di ritornare n* fact (n-1). però non sa quanto vale fact (n-1) e quindi va a calcolarlo chiamando fact (1) (nota che le variabili utilizzate nella prima chiamata rimangono salvate in memoria ad aspettare che la fact (1) faccia il suo sporco lavoro).

2: siamo scesi in fact (1) mentre fact (2) attende un risultato. 1 è diverso da 0 quindi ancora tenta di ritornare n* fact (n-1) ma deve calcolarlo e chiama la funzione fact (0) (anche qui fact (1) resta paziente in attesa).

3: riceve 0 e quindi la funzione passa 1 a quella che la precede e termina.

4: Siamo tornati in fact (1) che a questo punto è in grado di ritornare n* fact (n-1) che fa 1 e fatto ciò termina e libera la memoria che ha utilizzato.

5: fact (2) è in grado di ritornare a sua volta n* fact (n-1) che fa 2 e termina.

Tenendo a mente il discorso fatto sopra ti faccio ora un esempio con la visita inorder di un albero binario visto che te li hanno fatti fare. Consideriamo per esempio il seguente albero: (metto come codice solo per rendere più chiara la forma)

    6
   / \
  4   9
 / \
2   8

e consideriamo la seguente funzione che è abbastanza famosa o comunque molto utilizzata:

void inOrder (tree *node) {  /*node è un puntatore a struct tree*/
    if (node== NULL) return;
    inorder (node-> left); /* left e right sono puntatori al figlio sinistro e destro */
    visit (node); /* visit esegue una qualsiasi operazione sul nodo, ma a noi non interessa */
    inorder (node-> right);
}

- La prima chiamata riceve in input il puntatore al nodo 6. Il puntatore non è nullo quindi chiama inOrder () relativa al nodo 4.

- Ancora non è nullo quindi chiama inOrder relativa al nodo 2.

- Il puntatore a 2 non è nullo e chiama inOrder del figlio sinistro di 2.

- Il figlio sinistro di due non c'è quindi il suo puntatore è nullo. Ritorna.

- A questo punto ritorna sul nodo 2 e lo visita.

- Scende al figlio destro di 2 che non c'è e quindi ritorna a 2.

- Torna a 4 e lo visita.

- Scende sul figlio destro di 4 e tenta di visitarne il figlio sinistro, ma 8 non ce l'ha e quindi visita 8.

- Tenta di visitare il figlio destro di 8, ma 8 non ce l'ha e quindi ritorna a 4 e successivamente a 6 e visita 6.

- A questo punto scende al figlio destro di 6 e tenta di visitarne il figlio sinistro che non c'è e quindi visita 9.

- Tenta ancora di visitare il figlio destro di 9 ma non c'è e quindi torna a 9 e poi a 6 e infine termina.

Riassumendo, l'ordine di visita è 2 4 8 6 9.
Inoltre vorrei precisare che una funzione ricorsiva è una funzione che chiama una copia di sè stessa e non sè stessa perchè lei e la sua copia operano su input differenti e comunque il loro rapporto si limita allo scambio di informazioni. Differenza sottile ma comunque differenza.
Se ho sbagliato qualcosa correggetemi e non crocifiggetemi , comunque spero di essere stato utile

(fonti: corso di algoritmi e programmazione al polito)