Molte strutture dati (liste concatenate, alberi, ecc) sono definite in modo ricorsivo, dunque gli algoritmi ricorsivi risultano spesso più naturali di quelli iterativi. Tuttavia, eseguendo un numero eccessivo di chiamate ricorsive si rischia di saturare la memoria disponibile per lo stack, e ogni chiamata di funzione ha anche un certo costo in termini di tempo (per la gestione del record di attivazione), quindi dei linguaggi di programmazione “tradizionali” si tendono a preferire le versioni iterative di algoritmi naturalmente ricorsivi.
In realtà, come si vedrà a breve, ci sono delle situazioni in cui la ricorsione può essere implementata in un modo che non è meno efficiente dell’iterazione (se il compilatore / interprete lo supporta), e allora le due strategie possono essere considerate equivalenti.
Nella pratica, i linguaggi funzionali sono implementati, come quelli imperativi, sulla macchina di von Neumann, usando il modello di esecuzione a stack, dunque le considerazioni sull’efficienza della ricorsione andrebbero fatte ragionando su tale modello. Tuttavia, il principio che permette un’implementazione efficiente della ricorsione in determinate situazioni vale anche se si ragiona a più alto livello, considerando il modello di sostituzione, che è il modello della macchina astratta sulla quale si “immagina” che i programmi funzionali vengano eseguiti. Il primo passo per studiare questo principio è formalizzare la valutazione delle applicazioni di funzioni nel modello di sostituzione.
Si consideri una generica definizione di funzione:
$$ \texttt{def } f(x_1: \ T_1, \ \dots, \ x_n: T_n): \ T = B $$
La valutazione dell’applicazione di funzione $f(e_1, \dots, e_n)$ con la strategia call-by-value avviene, intuitivamente, nel modo seguente:
Ciò è formalizzato come un rewriting dell’intero programma:
La notazione $[v_1/x_1, \ \dots, \ v_n/x_n]$ indica una sostituazione (essa è la notazione standard per le sostituzioni nell’ambito dei linguaggi formali); in particolare, questa sostituzione sostituisce a ciascuna variabile (parametro formale) $x$, il valore $v_1$. L’applicazione di questa sostituzione, che qui per comodità viene indicata scrivendo la sostituzione a sinistra dell’espressione a cui la si applica, $[v_1/x_1, \ \dots, v_n/x_n]B$, ha appunto l’effetto di sostituire tutte le occorrenze di una variabile $x$, in $B$ con il valore $v_i$.
Uno degli esempi di funzioni ricorsive viste in precedenza è la funzione $\texttt{gcd}$:
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
Si vuole studiare la valutazione dell’applicazione $\texttt{gcd(14, 21)}$. Per semplicità, nello scrivere i passi di valutazione si mostrerà solo la parte del programma relativa all’applicazione della funzione, mentre in teoria il modello di sostituzione dovrebbe operare sull’intero programma, che comprende anche la definizione della funzione.
Siccome i parametri attuali presenti nell’applicazione $\texttt{gcd(14, 21)}$ sono letterali, che per semplicità si considerano già valutati (assimilandoli ai valori astratti che essi rappresentano), la prima cosa da fare è applicare la regola di riscrittura per le applicazioni di funzione appena presentata:
$$ \texttt{gcd(14, 21)} \\ \ \ \rarr \texttt{[14/a, 21/b](if (b == 0) a else gcd(b, a \% b))}
$$
Adesso si applica la sostituzione; ciò avviene contemporaneamente su tutte le variabili sostituite, in un unico passo di valutazione: