Dall’iterazione alla ricorsione

Descrizione del problema

In Haskell, lo strumento fondamentale per la realizzazione di algoritmi iterativi è la ricorsione. Tuttavia, vi sono casi in cui la versione ricorsiva di un algoritmo iterativo non è immediata da individuare oppure è obiettivamente inefficiente. Un tipico esempio è la funzione che calcola il $k$ -esimo numero nella sequenza di Fibonacci (che chiameremo per brevità “funzione di Fibonacci”). La sua versione funzionale/ricorsiva è indubbiamente elegante, ma ha complessità esponenziale in $k$ :

fibonacci :: Int -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci k = fibonacci (k - 1) + fibonacci (k - 2)

In netto contrasto, una classica realizzazione imperativa/iterativa della funzione di Fibonacci ha complessità lineare in $k$ . Qui sotto vediamo una versione in Java:

public static int fibonacci(int k) {
    assert k >= 0;
    int m = 0;
    int n = 1;
    while (k > 0) {
        n = n + m;
        m = n - m;
        k = k - 1;
    }
    return m;
}

Un altro esempio di algoritmo iterativo che non ammette un’ovvia versione ricorsiva è quello che determina se un certo numero $n$ è primo o no. Una realizzazione in Java di tale algoritmo è la seguente:

public static boolean primo(int n) {
    assert n >= 0;
    int k = 2;
    while (k < n && n % k != 0) k++;
    return k == n;
}

In questo esempio, la difficoltà nell’individuare una versione ricorsiva dell’algoritmo è dovuta al fatto che la primalità di un certo numero $n$ è del tutto scorrelata dalla primalità di $n - 1$ o di un qualsiasi altro numero più piccolo di $n$ . Di conseguenza, non è ovvio come impostare il caso induttivo di una ipotetica funzione ricorsiva equivalente.

In questo caso di studio vedremo come ottenere realizzazioni ricorsive con complessità lineare della funzione di Fibonacci e del test di primalità. La tecnica illustrata è generale e può essere usata per trasformare algoritmi imperativi/iterativi in funzionali/ricorsivi.

Soluzione ricorsiva lineare di Fibonacci

Osserviamo che l’implementazione Java della funzione di Fibonacci agisce su uno stato che comprende, oltre al parametro $k$ della funzione, anche due variabili locali. L’idea è quella di impostare una funzione ricorsiva che ha tanti argomenti quante sono le variabili locali usate dall’algoritmo iterativo, simulando la modifica di una variabile locale con una opportuna chiamata ricorsiva. Seguendo questa intuizione, nel caso di fibonacci otteniamo una funzione fibonacciAux definita come segue:

fibonacciAux :: Integer -> Integer -> Int -> Integer
fibonacciAux m _ 0 = m
fibonacciAux m n k = fibonacciAux n (m + n) (k - 1)

Abbiamo chiamato questa funzione fibonacciAux e non fibonacci per sottolineare il fatto che tale funzione non risolve il problema originario, bensì uno più generale. Più precisamente, se indichiamo con $F_{n}$ l’ $n$ -esimo numero nella sequenza di Fibonacci, possiamo dimostrare che

$fibonacciAux F_{n} F_{n + 1} k = F_{n + k}$

per ogni $k \geq 0$ . Procediamo per induzione su $k$ . Nel caso base, quando $k = 0$ abbiamo

\begin{array}{rcll} fibonacciAux F_{n} F_{n + 1} k & = & F_{n} & per definizione di fibonacciAux \\ = & F_{n + k} & dal momento che k = 0 \end{array}

Se $k > 0$ , allora abbiamo

\begin{array}{rcll} fibonacciAux F_{n} F_{n + 1} k & = & fibonacciAux F_{n + 1} (F_{n} + F_{n + 1}) (k - 1) & per def. di fibonacciAux \\ = & fibonacciAux F_{n + 1} F_{n + 2} (k - 1) & per definizione di F_{n + 2} \\ = & F_{n + 1 + k - 1} & per ipotesi induttiva \\ = & F_{n + k} \end{array}

Notiamo che il caso base di fibonacciAux corrisponde alla condizione di terminazione del ciclo while nella versione Java: se k è 0 il risultato è m. Dualmente, il caso ricorsivo di fibonacciAux corrisponde all’esecuzione di una iterazione del ciclo while: se k è maggiore di 0, allora il risultato è ottenuto ponendo m a n, n a m + n e k a k - 1. Queste modifiche di m, n e k sono ottenute nella versione Java con assegnamenti che modificano lo stato. Nella versione Haskell otteniamo un effetto analogo applicando ricorsivamente fibonacciAux alle versioni modificate di m, n e k. Tra l’altro, in questo modo non dobbiamo preoccuparci del fatto che m ed n devono essere modificate con un gioco di prestigio di somme e sottrazioni oppure usando una terza variabile di appoggio.

Resta il fatto che fibonacciAux non è la funzione che risolve il problema originario, ma possiamo ottenere fibonacci come semplice specializzazione di fibonacciAux:

fibonacci :: Int -> Integer
fibonacci = fibonacciAux 0 1

Il modo in cui fibonacciAux è applicata corrisponde all’inizializzazione di m ed n nella versione Java. Possiamo ulteriormente raffinare questa soluzione osservando che l’utilità della funzione ausiliaria fibonacciAux è limitata alla funzione fibonacci. Per tale motivo ha senso definire fibonacciAux come funzione locale di fibonacci, in un blocco di codice indentato che segue la parola chiave where:

fibonacci :: Int -> Integer
fibonacci = aux 0 1
  where
    aux m _ 0 = m
    aux m n k = aux n (m + n) (k - 1)

Definire localmente la funzione ausiliaria ci consente, tra le altre cose, di darle un nome più conciso senza rischiare conflitti con altre funzioni omonime, e rende meno importante documentarla con una annotazione di tipo esplicita, che dunque omettiamo.

Soluzione ricorsiva del test di primalità

Come per fibonacci, anche l’implementazione Java del test di primalità agisce su uno stato che comprende il parametro $n$ della funzione e una variabile locale $k$ che viene fatta scorrere su tutti i candidati divisori di $n$ , da 2 a $n - 1$ . A differenza della funzione di Fibonacci notiamo che solo $k$ cambia da una iterazione all’altra, mentre $n$ non è mai modificato. Questo suggerisce una realizzazione Haskell con una funzione ricorsiva che ha un unico argomento $k$ , come mostrato di seguito:

primo :: Int -> Bool
primo n = aux 2
  where
    aux k | k >= n         = k == n
          | n `mod` k == 0 = False
          | otherwise      = aux (k + 1)

Notiamo in particolare che la funzione ausiliaria aux può accedere al parametro n della funzione primo, all’interno della quale è localmente definita. Notiamo inoltre la solita corrispondenza tra casi base di aux e condizioni di terminazione del ciclo nella versione Java di primo. Il ciclo termina se k >= n, nel qual caso abbiamo testato tutti i candidati divisori di n senza trovarne alcuno, e dunque restituiamo True o False a seconda che k sia uguale o maggiore di n, rispettivamente. Il ciclo termina anche se k divide n, il che significa che abbiamo trovato un divisore di n e dunque possiamo concludere che n non è primo. Il caso induttivo della ricorsione corrisponde a una iterazione del ciclo, in cui ci limitiamo ad aggiornare k al candidato successivo. Proprio come nel caso della funzione di Fibonacci, anche qui l’applicazione aux 2, che dà il via alla ricorsione, corrisponde all’inizializzazione di k nella versione Java dell’algoritmo.

Esercizi

Scrivere una funzione ricorsiva corrispondente al seguente algoritmo iterativo:

public static int fattoriale(int n) {
    assert n >= 0;
    int res = 1;
    while (n > 0) {
       res = res * n;
       n = n - 1;
    }
    return res;
}

fattoriale :: Int -> Int
fattoriale = aux 1
  where
    aux res 0 = res
    aux res n = aux (res * n) (n - 1)

Scrivere una funzione ricorsiva corrispondente al seguente algoritmo iterativo:

public static int bits(int n) {
    assert n >= 0;
    int bits = 0;
    while (n > 0) {
        bits = bits + n % 2;
        n = n / 2;
    }
    return bits;
}

bits :: Int -> Int
bits = aux 0
  where
    aux bits 0 = bits
    aux bits n = aux (bits + n `mod` 2) (n `div` 2)

Scrivere una funzione ricorsiva corrispondente al seguente algoritmo iterativo:

public static int euclide(int m, int n) {
    assert m > 0 && n > 0;
    while (m != n)
        if (m < n) n -= m; else m -= n;
    return n;
}

euclide :: Int -> Int -> Int
euclide m n | m == n    = m
            | m < n     = euclide m (n - m)
            | otherwise = euclide (m - n) n