regola ricorsiva

regola ricorsiva

regola ricorsiva regola che, nella propria formulazione, “richiama sé stessa”. Tale richiamo non è tuttavia una sorta di circolo vizioso perché una regola ricorsiva definisce un oggetto non in termini di sé stesso bensì di una sua versione più semplice. Per esempio, è possibile definire ricorsivamente una stringa non vuota (cioè una sequenza di uno o più caratteri di un dato alfabeto) con le due seguenti regole:

• una stringa può essere un carattere,

• una stringa può essere un carattere seguito da una stringa.

La seconda regola è ricorsiva. Analogamente, si può dare una definizione costruttiva di numero naturale in modo ricorsivo con le seguenti regole (dove numnat indica un generico numero naturale e s la funzione → successore definita in N):

• numnat = 0

• numnat = s(numnat)

In informatica, o più in generale nelle descrizioni formali delle procedure di calcolo, una regola ricorsiva (detta anche procedura ricorsiva) indica uno schema di calcolo che permette di risolvere un problema attraverso il richiamo ripetuto dello stesso schema applicato però a un caso via via di minore complessità, riducendo così il problema stesso a problemi progressivamente più semplici. Per esempio, il calcolo del fattoriale di un numero naturale n, indicato con il simbolo n!, dopo aver fissato il valore iniziale, cioè il valore 0! = 1, può essere formalizzato tramite una regola ricorsiva, del tipo n! = n(n − 1)! che indica che il fattoriale del numero n è uguale al prodotto di n per il fattoriale del suo predecessore. Così il calcolo di 8! è costruito ricorsivamente fino a giungere al valore iniziale:

Operativamente, una regola ricorsiva sospende l’esecuzione del calcolo al passo n e richiama l’applicazione di sé stessa al passo precedente, che a sua volta sospende la propria esecuzione richiamando la sua applicazione al passo precedente e così via; quando si giunge al passo iniziale, si calcola il valore nel caso base e s’iniziano a chiudere tutte le procedure lasciate in sospeso. Per poter realizzare un simile schema, ogni procedura aperta deve essere memorizzata in una pila, cioè una struttura di dati in cui l’ultimo dato immesso è il primo a essere accessibile. Il vantaggio di utilizzare uno schema ricorsivo nella progettazione di un algoritmo consiste, quindi, nel limitato uso dei contatori, al contrario di quanto avviene per le procedure iterative. Dal punto di vista dell’automa, il calcolo ricorsivo richiede però una migliore capacità di organizzazione della memoria e una sua maggiore estensione per la memorizzazione delle pile degli argomenti della procedura. Il principio alla base delle regole ricorsive è applicato anche nella definizione di una importante classe di funzioni, le → funzioni ricorsive, le quali hanno il ruolo di tradurre in termini formali il concetto intuitivo di funzione calcolabile.