3 Binomiali per ricorsione lineare

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:

(n)    (n - 1) n
    =          --,    0 < k < n.
 k      k - 1   k
(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.

Esercizio scrivere una funzione ricorsiva BinCoeff2, con testa
DEF BinCoeff2 =

utilizzando la definizione (4) ed effettuare numerosi test.

Esercizio scrivere una funzione PLaSM denominata RigaTartaglia, con testa

DEF RigaTartaglia (n::IsNat) =

che calcoli la riga n-esima del triangolo di Tartaglia