funzione definita ricorsivamente

funzione definita ricorsivamente

funzione definita ricorsivamente funzione di dominio N i cui valori sono determinabili attraverso passi successivi di calcolo, tali che, assegnato il suo valore iniziale, il valore della funzione a un certo passo n si basi sul valore della stessa funzione al passo n − 1. Si consideri come esempio la funzione S(n) che associa a ogni numero naturale la somma di tutti i numeri naturali da 0 a n: S(0) = 0, S(1) = 1, S(2) = 3, S(3) = 6, ... tale funzione può essere definita ricorsivamente in questo modo:

Il calcolo effettivo di una tale funzione da parte di un automa procede “impilando” i successivi risultati parziali e si risolve soltanto quando si raggiunge il passo iniziale. Per esempio:

Una funzione definita ricorsivamente può così essere calcolata tramite un algoritmo ricorsivo (→ calcolo ricorsivo; → funzione ricorsiva; → funzione ricorsiva primitiva).