[程式]以tail-recursion來實作已有iterative求解法的recursive數學函數

最近和同好討論到程式方面的問題。對於一個缺乏iterative loop機制的函數式程式語言，要如何做到類似for loop的計算動作呢?最簡單的方法是，在這個函數本體中放入每回iteration時要做的計算動作，在計算動作完成後，呼叫函數自身，並且把要傳到下一輪iteration的數值做為呼叫函數所需的參數。只要這個函數的寫法符合tail-recursive規範，執行於任何有實作tail-recursive最佳化的函數式程式語言(如Scheme、Erlang等等)，就不會發生因recursion次數太多造成stack overflow的問題。

當我們要用C語言這類循序式程式語言計算Fibonacci數列中第n個數值是多少時，在n>1的前提下可以用

f(n)<=f(n-1)+f(n-2)

以recursive求解。但是當n很大時，會發生stack overflow的問題，再加上每回求解時，f(n-1)自身也需要用到f(n-2)的結果，使得重複計算的問題持續發生。 既然如此，用iterative的實作方法既能迴避stack overflow，又能重複利用前一輪的計算結果，根本是兩全齊美!但要以缺乏iterative loop機制的函數式程式語言，來實作iterative版的Fibonacci數列求解時，我們就得用點小技巧了。 像是以Lisp-1家族的Scheme來寫Fibonacci函數時，在tail-recursion這部分，除了原有的參數n之外，還要把中間結果a與b做為呼叫函數所需的參數，傳到下一輪iteration：

(define (fibonacci n)
    (define (fibonacci_internal n a b)
        (if (> n 0)
            (fibonacci_internal (- n 1) b (+ a b))
            a))
    (fibonacci_internal n 0 1))

把這段Scheme程式碼拿到支援大數計算的直譯器跑(例如較新版的GNU Guile)，就會發現，不論n有多大，這個Fibonacci函數都不會因為stack overflow而當機，也不會因為integer的數值overflow而出現預期外的結果。唯一麻煩的地方，是需要另外定義外部函數fibonacci來包裝函數的參數介面，讓呼叫者不用直接面對需要傳遞a與b的核心函數fibonacci_internal，並在開始執行時自動給a與b一個起始值。

若要循序列舉上述Fibonacci函數的return值，我們也可以用tail-recursive的寫法來循序列出Fibonacci函數求解結果：

(define (loop_test n)
    (define (iter i n)
        (format #t "fibonacci(~a)=~a" i (fibonacci i))
        (newline)
        (if (< i n)
            (iter (+ i 1) n)))
    (iter 0 n))