calcolo ricorsivo

calcolo ricorsivo

calcolo ricorsivo procedimento di calcolo che risolve un problema di una data complessità riducendolo a problemi via via più semplici. Il valore di una funzione definita ricorsivamente a un dato passo n, indicato con ƒ(n), viene calcolato attraverso il valore della stessa funzione al passo n − 1, cioè ƒ(n − 1), che a sua volta viene calcolato per mezzo di ƒ(n − 2) fino ad arrivare al valore ƒ(0). Un esempio di funzione che può essere definita ricorsivamente è il fattoriale di un numero naturale n, indicato con il simbolo n! (da leggersi «n fattoriale»). Il valore della funzione n! è uguale al prodotto di tutti i numeri naturali non nulli minori o uguali a n (3! = 3 · 2 · 1 = 6; 4! = 4 · 3 · 2 · 1 = 24; ...). Questa funzione può essere calcolata in maniera ricorsiva, infatti n! = n · (n − 1)!. Il valore della funzione al passo n è stato quindi scritto sulla base del suo valore al passo n − 1. Si può continuare in questo modo fino al valore della funzione al passo iniziale. Questo schema di calcolo è largamente utilizzato nella programmazione attraverso la definizione di procedure basate sul calcolo ricorsivo e dette procedure ricorsive. Il calcolo di una procedura ricorsiva si sospende al passo n e richiama lo stesso calcolo al passo precedente che a sua volta si sospende e richiama quello al passo precedente e così via; quando si giunge al passo iniziale, si calcola la funzione 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, ovvero 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 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 perché, se si devono realizzare molti livelli di ricorsione, occorre molta memoria per le pile degli argomenti della procedura.