[C] Ricorsione... Come,Quando e Perche' ?

[nightfall]

1. Quando si usa la Ricorsione...?
2. Perche' si usa la Ricorsione...?
3. Come si usa la Ricorsione...?

Grazie...

[kentaromiura]

1)quando una procedura richiama se stessa
2)esempio il fattoriale di N si calcola
N*N-1*...*1
3)

f(int i){
if (i=1) return 1;
else return f(i-1);
}

[nightfall]

...Non e' che avresti un esempio diverso...
Su tutti i libri c'e' quello

...Grazie Comunque..

[cristiano_longo]

Esempio classico e' la visita di un albero. Non ti posto il codice che e' un po complicato. Un albero e' una struttura definita di per se' ricorsivamente nel seguente modo

caso base) Una foglia e' un albero
caso ricorsivo) Un nodo che ha degli alberi come figli e' a sua volta un albero.

In genere, quando crei una funzione ricorsiva, devi distinguere un caso base, al quale si ferma la ricorsione, ed un caso ricorsivo, nel quale la funzione richiama se stessa.

Nel caso della visita dell'albero, la funzione viene pressappoco così

1:funzione visita(nodo n)
2:  stampa(n)
3:  se n è una foglia(caso base) fine;
4:  se n non e' una foglia (caso ricorsivo)
5:    per ogni m figlio di n
6:       visita(m)

Oltre a rendere spesso più semplici e leggibili gli algoritmi, la ricorsione ha il grande vantaggio di facilitare le dimostrazioni di correttezza degli algoritmi stessi.

Per verificare un algoritmo ricorsivo la dimostrazione segue due semplici passi

1)dimostrare che funziona nel caso base
2)presupponendo che per un gerico input funziona, dimostrare che funziona per quello subito più "grande"

Per spiegare cosa si intende per più grande torniamo all'esempio precedente. La dimostrazione del passo induttivo (2) diventa

Sia t un albero con figli che ha n come radice e t1, ..., tk
come sottoalberi figli di n. Presupposto che l'algoritmo funziona per t1,..., tk dimostrare che funziona anche per t.

Attenzione : il post contiene un bel po di imprecisioni.

[infinitejustice]

Io la ricorsione la usai in una simulazione di labirinto.

n mosse, la funzione che ti faceva muovere richiamava se stessa passandosi n-1 mosse disponibili rimaste fino a quando n > 0.

Il pro della ricorsione è che ti permette di avere un codice molto compatto ed elegante

Il contro è che porta via parecchia memoria