Se ti hanno parlato di ricorsione, ti avranno fatto il super classico esempio:
definizione di fattoriale:
il fattoriale di N (scritto come N!) e' il prodotto dei numeri 1*2*3*...*N
che cosa e' il fattoriale di N-1? Il prodotto dei numeri 1*2*3*...*(N-1)
quindi il fattoriale di N puo' essere scritto come il fattoriale di N-1 PER N
Usando una pseudosintassi, la definizione di fattoriale potrebbe essere scritta come:
fattoriale(N) := fattorial(N-1)*N
Ecco la definizione ricorsiva di fattoriale: la definizione dipende da se stessa!
Ora qui' nasce il problema: se il fattoriale di N dipende dal fattoriale di N-1, che dipende dal fattoriale di N-2 ... che dipende dal fattoriale di 2, che dipende dal fattoriale di 1 che dipende ...
Quando ci si ferma?
Serve una condizione che blocchi la ricorsione: la cosidetta base della ricorsione.
La base della ricorsione, nel caso del fattoriale, e' la seguente: per definizione, il fattoriale di 0 e' 1 (uno).
Quindi, la definizione ricorsiva di fattoriale, avrebbe una forma del tipo:
fattoriale(N) := (N == 0) ? 1 : fattoriale(N-1)*N.
Qui ci sono tutti i concetti fondamentali necessari per la realizzazione di una funzione ricorsiva:
1) la funzione deve essere definita in base a se stessa, ma ci deve essere qualcosa che cambia, e che va verso la base della ricorsione
2) ci deve essere la base della ricorsione, che blocca la ricorsione.
Un'altro super stra classico esempio di definizione ricorsiva e' il principio di indizione:
se un certo predicato P e' vero per 0, ed il fatto che sia vero per N implica che sia vero per N+1, allora il predicato e' vero per ogni N.
Poi ci sono diverse varianti:
1) invece di partire da 0 si potrebbe partire da K > 0.
2) invece di passare da N a N+1, si puo' passare da N-1 a N