La precedente implementazione, che fa uso delle equazioni (2) e (3), è altamente inefficiente. Infatti, il calcolo di un singolo numero binomiale richiede il calcolo di molti altri numeri di questo tipo e, peggio ancora, molti di questi sono calcolati e ricalcolati molte volte. Una soluzione molto migliore si ottiene usando nel caso ricorsivo la equazione:
| (4) |
In questo modo, la funzione fa una sola chiamata a se stessa nel caso ricorsivo, invece di due. Un metodo di questo tipo, dove una funzione ricorsiva chiama se stessa al massimo una sola volta, è chiamato ricorsione lineare.
DEF BinCoeff2 = |
Esercizio scrivere una funzione PLaSM denominata RigaTartaglia, con testa
DEF RigaTartaglia (n::IsNat) = |