如何將以下內容轉換爲尾遞歸過程？

Question

我有以下的數學表達式爲：

; f(n) = f(n - 1) + f(n - 2) where n >= 2 
; f(n) = n where n < 2` 

其中我翻譯成一個正常的遞歸調用LISP：

(define (f n) 
    (cond ((< n 2) n) 
     (else (+ (f (- n 1)) 
       (f (- n 2)))))) 

我將如何轉換到上述尾遞歸過程？我不習慣功能性編程，所以我掙扎了一下。

Answer 1

您正在討論計算斐波那契數的尾遞歸變換的已建立示例。您可以在SICP的this chapter找到代碼示例的極佳描述。

Answer 2

（下面的代碼編寫和測試Racket。）

開始與天真的版本：

;; fib : nat -> nat 
(define (fib n) 
    (cond [(= n 0) 0] 
     [(= n 1) 1] 
     [else (+ (fib (- n 1)) (fib (- n 2)))])) 

當我們開發新的版本，我們可以使用test，看看他們是否與同意最初fib（至少在數字0到9）。

;; test : (nat -> nat) -> boolean 
;; Check that the given function agrees with fib on 0 through 9 
(define (test f) 
    (for/and ([i (in-range 10)]) 
    (= (f i) (fib i)))) 

首先，關鍵的觀察，讓一切的是，當我們計算(fib N)，我們已經計算(fib (- N 1)) ...但我們丟棄它，所以我們要稍後再重新計算的。這就是爲什麼天真fib是指數時間！我們可以做到通過保持它周圍好，說與返回一個列表中的輔助功能：

;; fib2list : nat -> (list nat nat) 
;; (fib2list N) = (list (fib (- N 1)) (fib N)) 
(define (fib2list n) 
    (cond [(= n 1) (list 0 1)] 
     [else (let ([resultN-1 (fib2list (- n 1))]) 
       (let ([fibN-2 (first resultN-1)] 
         [fibN-1 (second resultN-1)]) 
        (list fibN-1 
         (+ fibN-2 fibN-1))))])) 

;; fib2 : nat -> nat 
(define (fib2 n) 
    (cond [(= n 0) 0] 
     [else (second (fib2list n))])) 

(test fib2) ;; => #t 

的fib2list功能停在1，所以fib2處理0作爲一個特殊的（但不感興趣的）情況。

我們可以延續傳遞風格（CPS）重寫這使它尾遞歸：

;; fib3k : nat ((list nat nat) -> nat) -> nat 
(define (fib3k n k) 
    (cond [(= n 1) (k (list 0 1))] 
     [else (fib3k (- n 1) 
        (lambda (resultN-1) 
         (let ([fibN-2 (first resultN-1)] 
          [fibN-1 (second resultN-1)]) 
         (k (list fibN-1 
            (+ fibN-2 fibN-1))))))])) 

;; fib3 : nat -> nat 
(define (fib3 n) 
    (cond [(= n 0) 0] 
     [else (fib3k n (lambda (resultN) 
         (let ([fibN-1 (first resultN)] 
           [fibN (second resultN)]) 
          fibN)))])) 

(test fib3) ;; => #t 

現在反而讓一個非尾遞歸調用，fib3k電話本身具有擴展的延續，需要一個列表結果。 (fib3k N k)的延續k被稱爲等效於(list (fib (- N 1)) (fib N))的列表。 （因此，如果第一個參數爲(- n 1)，所述延續參數被命名爲resultN-1等）

要開始關閉一切，我們提供了一個初始延續，是以結果resultN;第二個元素等於(fib N)，所以我們返回。

當然，沒有理由繼續打包列表;我們可以只讓繼續採取兩個參數：

;; fib4k : nat (nat nat -> nat) -> nat 
(define (fib4k n k) 
    (cond [(= n 1) (k 0 1)] 
     [else (fib4k (- n 1) 
        (lambda (fibN-2 fibN-1) 
         (k fibN-1 
          (+ fibN-2 fibN-1))))])) 

;; fib4 : nat -> nat 
(define (fib4 n) 
    (cond [(= n 0) 0] 
     [else (fib4k n (lambda (fibN-1 fibN) fibN))])) 

(test fib4) ;; => #t 

請注意，只有兩個變種繼續參與此計劃的 ---它們對應的代碼的兩次出現lambda。有最初的延續，並有延伸現有延續的單一方式。使用這種觀察，我們可以變換延續功能集成到一個上下文數據結構：

;; A context5 is either 
;; - (initial-context) 
;; - (extend-context context5) 
(struct initial-context()) 
(struct extend-context (inner)) 

現在我們替換創建延續功能（即，lambda多個）表達與所述的用途上下文構造函數，我們用一個新的明確的apply-context5函數替換應用了繼續函數的（單個）站點，該函數執行之前由兩個lambda表達式完成的工作：

;; fib5ctx : nat context5 -> nat 
(define (fib5ctx n ctx) 
    (cond [(= n 1) (apply-context5 ctx 0 1)] 
     [else (fib5ctx (- n 1) 
         (extend-context ctx))])) 

;; apply-context5 : context5 nat nat -> nat 
(define (apply-context5 ctx a b) 
    (match ctx 
    [(initial-context) 
    b] 
    [(extend-context inner-ctx) 
    (apply-context5 inner-ctx b (+ a b))])) 

;; fib5 : nat -> nat 
(define (fib5 n) 
    (cond [(= n 0) 0] 
     [else (fib5ctx n (initial-context))])) 

(test fib5) ;; => #t 

（當編譯器做到這一點，他們叫它去官能化或關閉的轉換，他們這樣做是爲了把間接跳轉到直接跳轉）。

在這一點上，這真的很明顯，context數據類型是完全無聊。實際上，它的代數等價於自然數！ （一個自然數或者是零，或者是自然數的後繼數。）所以讓我們改變上下文數據類型來使用自然數而不是一些堆分配結構。

;; A context6 is just a natural number. 

;; fib6ctx : nat context6 -> nat 
(define (fib6ctx n ctx) 
    (cond [(= n 1) (apply-context6 ctx 0 1)] 
     [else (fib6ctx (- n 1) 
         (+ ctx 1))])) 

;; apply-context6 : context6 nat nat -> nat 
(define (apply-context6 ctx a b) 
    (cond [(= ctx 0) 
     b] 
     [else 
     (apply-context6 (- ctx 1) b (+ a b))])) 

;; fib6 : nat -> nat 
(define (fib6 n) 
    (cond [(= n 0) 0] 
     [else (fib6ctx n 0)])) 

(test fib6) ;; => #t 

但現在很明顯，fib6ctx只是計數ctx了，因爲它計算n下降到1。特別是：

(fib6ctx N M) = (fib6ctx 1 (+ N M -1)) 
       = (apply-context6 (+ N M -1) 0 1) 

等

(fib6ctx N 0) = (apply-context6 (+ N -1) 0 1) 

因此，我們可以擺脫完全可以使用fib6ctx。

;; apply-context7 : nat nat nat -> nat 
(define (apply-context7 ctx a b) 
    (cond [(= ctx 0) 
     b] 
     [else 
     (apply-context7 (- ctx 1) b (+ a b))])) 

;; fib7 : nat -> nat 
(define (fib7 n) 
    (cond [(= n 0) 0] 
     [else (apply-context7 (- n 1) 0 1)])) 

(test fib7) ;; => #t 

這就是斐波那契的傳統迭代版本，除了apply-context7通常被稱爲fib-iter或類似的東西，和大多數版本的計數，而不是向下的，希望他們得到比較正確的，使他們沒有得到一個一次錯誤。