PDA

Visualizza la versione completa : [C] Ricorsione... Come,Quando e Perche' ?


nightfall
10-12-2003, 15:05
1. Quando si usa la Ricorsione...?
2. Perche' si usa la Ricorsione...?
3. Come si usa la Ricorsione...?

Grazie...

kentaromiura
10-12-2003, 15:10
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
10-12-2003, 15:11
...Non e' che avresti un esempio diverso...
Su tutti i libri c'e' quello :dh:

...Grazie Comunque..

cristiano_longo
10-12-2003, 15:28
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
10-12-2003, 15:42
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 :nonlodire

Loading