Ricorsione

Le strutture di controllo di iterazione non sono disponibili nei linguaggi funzionali puri, perchè sono fortemente legate al paradigma imperativo (ad esempio, la condizione di ciclo while può diventare false solo se cambia il valore di almeno una delle variabili che vi compaioni). Tuttavia l’iterazione è sostanzialmente un modo “sporco” di fare ciò che in matematica viene fatto con la ricorsione. Un classico esempio di funzione ricorsiva è la funzione fattoriale (qui indicata con l’operatore postfisso !, ma si potrebbe usare equivalentemente la normale notazione delle funzioni),

$$ n! = \begin{cases} 1 &\text{se } n = 0 \\ n * (n-1)! &\text{altrimenti} \end{cases} $$

che può essere tradotta quasi direttamente in Scala:

def factorial(n: Int): Int = 
	if (n == 0) 1 else n * factorial(n - 1)

(si noti che specificare il tipo restituito è obbligatorio, perchè la funzione factorial è ricorsiva).

Conversione dell’iterazione in ricorsione

Nell’esempio precedente si è scritta una funzione ricorsiva a partire da una definizione matematica già ricorsiva. Adesso, si vuole mostrare che anche una tipica iterazione imperativa è riducibile a meccanismi ricorsivi.

Come esempio di algoritmo iterativo, si consideri il calcolo di $n!$ mediante la strategia suggerita dalla seguente definizione:

$$ n! = 1* 2*3 \dots n $$

Il processo di calcolo può essere descritto usando due variabili:

• product contiene i prodotti parziali ottenuti a ogni fase del calcolo
• counter è un contatore che controlla il processo di iterazione, e al tempo stesso fornisce la successione di numeri crescenti che vengono usati per calcolare i prdototti parziali.

Entrambe le variabili sono inizializzate a 1 (perchè 1 è l’elemento neutro del prodotto e il primo numero considerato dalla definizione di fattoriale appena mostrata). Poi, a ogni iterazione, si modificano product e counter in questo modo:

$$ \texttt{product = product * counter \ \ \ counter = counter + 1} $$

Le iterazioni continuano fintantochè counter <= n.

In Java, questa strategia è implementata dal seguente metodo:

public static int factorial_iter(int n) {
	int product = 1, counter = 1;
	while (counter <= n) {
		product = product * counter;
		counter = counter + 1;
	}
	return product;
}

Esso non può essere “riscritto” direttamente come funzione in Scala, poichè non si dispone di meccanismi di iterazione (a meno di utilizzare gli aspetti imperativi del linguaggio). Tuttavia, come già anticipato, è possibile simulare questa strategia iterativa utilizzando la ricorsione. A scopo illustrativo, la versione ricorsiva verrà prima definita in Java, e poi tradotta in Scala.

L’idea è introdurre un metodo ricorsivo che simuli le variabili mutable coinvolte nell’iterazione usando invece dei parametri formali: