Introduzione
Ricorsione in coda
Una funzione è ricorsiva in coda se l'ultima cosa eseguita dalla funzione è una chiamata a se stessa.
Ogni volta che viene chiamata una funzione, uno stack frame con le sue variabili locali e i suoi argomenti viene messo in cima allo stack delle chiamate di funzione.
Quando una funzione termina, lo stack frame viene rimosso dallo stack.
Le funzioni ricorsive in coda consentono l'ottimizzazione delle chiamate in coda (o l'eliminazione delle chiamate in coda).
È un'ottimizzazione che permette di riutilizzare l'ultimo stack frame per la successiva chiamata di funzione, quando la funzione precedente non ne ha più bisogno.
Questo riduce il rischio di far traboccare lo stack delle chiamate di funzione, una situazione in cui ci sono così tanti frame sullo stack che non rimane memoria per crearne un altro.
L'ottimizzazione delle chiamate in coda in Elm
In alcune condizioni, il compilatore Elm è in grado di eseguire automaticamente un'ottimizzazione delle chiamate in coda quando compila in JavaScript.
L'ottimizzazione può avvenire per una funzione ricorsiva quando l'ultima operazione in un ramo consiste nel chiamare la funzione stessa in una semplice applicazione di funzione.
Vediamo alcuni esempi:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
L'implementazione qui sopra non è ricorsiva in coda, perché l'ultima operazione nel ramo else è una moltiplicazione n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
L'implementazione qui sopra è ricorsiva in coda e verrà ottimizzata, perché l'ultima operazione nel ramo else è factorialHelper che chiama se stessa.
Questo non sarebbe possibile per una funzione con la firma di tipo Int -> Int; in pratica, l'ottimizzazione delle chiamate in coda si ottiene spesso definendo funzioni ausiliarie.
Istruzioni
Piper è un'appassionata di torte.
Nessuno sa se ha iniziato a preparare le torte per via del suo nome, o se ha cambiato nome per farlo combaciare con il suo hobby.
A prima vista la seconda ipotesi non sembra molto probabile, ma Piper è letteralmente affascinata dalle torte.
Armeggia sempre in cucina, ritocca le sue ricette, migliora la sua arte, con grande gioia dei suoi amici.
Il suo ultimo interesse?
Preparare torte quanto più possibile circolari, fino alla perfezione matematica, con l'aiuto del suo numero preferito, indovinato: π.
Piper ha trovato una formula deliziosa per calcolare π in modo iterativo, la trasformazione di convergenza di Newton/Eulero:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Aiuta Piper a preparare la sua torta matematicamente perfetta calcolando π.
1. Fattoriale
Prima un po' di riscaldamento.
L'operatore fattoriale, di solito scritto !, è definito come
0! = 1
n! = 1 * 2 * 3 * ... * n
Definisci la funzione factorial, che calcolerà il fattoriale in modo ricorsivo in coda.
factorial 4
-- 24
2. Doppio fattoriale
L'operatore doppio fattoriale, di solito scritto !!, è definito come
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Definisci la funzione doubleFactorial, che calcolerà il doppio fattoriale in modo ricorsivo in coda.
factorial 5
-- 15
factorial 6
-- 48
Definisci la funzione pipersPi, che approssimerà π usando un numero fisso di termini della formula di trasformazione di convergenza di Newton/Eulero, in modo ricorsivo in coda.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Calcoliamo insieme il primo termine.
Con un limite superiore di 0 (invece che di infinito), otteniamo:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Ogni termine in più migliorerà l'approssimazione.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Esercizio di apprendimento
