3 Binomiali per ricorsione lineare

La precedente implementazione, che fa uso delle equazioni (1) e (2), è 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:

(3)

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

Esercizio scrivere una funzione PLaSM denominata RigaTartaglia, con testa