Le funzioni ricorsive SEMBRANO una cosa complicata ma in realtà sono abbastanza semplici da capire.
Puoi iniziare dal ‘principio di induzione’
se una cosa e' vera per 0 (zero)
E
SE la cosa è era per N (questo e' il dato di fatto, NON LO DEVI dimostrare, TI VIENE DETTO che e' vero) e si puo'dimostrare che e' vera per N +1
ALLORA
questa cosa e' vera per OGNI N.
Dove N e' un numero intero positivo.
https://it.m.wikipedia.org/wiki/Principio_d%27induzione
Se ci ragioni qualche se secondo, ti renderai conto che ha senso:
- e' vera per 0 (questo deve essere controllato SENZA USARE il principio di induzione)
- poiche' e' vera per 0, per il PdI e' vera per 1
- poiche e' vera per 1, per il PdI e' vera per 2
- …
.
Nota che qui la sequenza va da 0 a 1,2,3,…
Altro esempio superclassico, il FATTORIALE:
fact(n) = 1*2*3*…*(n-1)*n
Per convenzione
fact(0) vale 1
fact(1) vale 1
ora fact(n) lo puoi definire in modo ricorsivo come:
fact(n) =fact(n-1)*n
Ma quanto vale fact(n-1)?
fact(n-1) = 1*2*3*…*(n-1)
che moltiplicato per n ritorna ESATTAMENTE la formula iniziale.
Il ‘trip’ consiste in questo:
devo calcolare la funzione di un numero grande.
Ok, ‘spiezzo’ il calcolo in 2 parti, una parte che usa la stessa funzione su un numero un po' piu' piccolo, generalmente di 1 ma in certi casi si puo' fare di meglio, ed il resto.
Ora chiamo la funzione sul numero piu' piccolo e rifaccio lo stesso ragionamento.
Attenzione, qui' c'e' il ‘trucco' : ma se continuo a fare lo stesso lavoro su numeri SEMPRE PIU' PICCOLI, QUANDO mi fermo?
Serve il caso che si chiama ‘base della ricorsione’ dove NON USO LA FUNZIONE ricorsiva (la stessa cosa di 0 per il PdI)
Per il fattoriale e'
fact(0) e fact(1)
Nota che qui la sequenza e' all'incontrario:
n, n-1,…,3,2,1,0
Il che ha senso perche' in questo caso vogliamo DIMOSTRARE che una certa cosa e' valida per n SUPPONENDO che dia valida per n-1, ma che dobbiamo ancora controllare.
Si poteva ragionare stile PdI? Cioe' pretendo da 0?
Cetamente SI ed e' esattamente quello che si fa con i cicli.
Ma allora si possono usare i cicli per calcolare le funzioni ricorsiva senza farsi di ‘acido’?
Assolutamente SI, MA molto spesso la definizione ricorsiva puo' risultare estremamente piu' semplice da scrivere che non mediante i cicli, soprattutto quando l'oggetto coinvolto non e' una ‘sequenza’, come nei casi visti sopra, MA un struttura ad ‘albero’ come, ad esempio, il filesystem del computer