延續傳球風格讓事情尾巴遞歸？

Question

很痛，在這裏問一下。它確實如此。每次我徒勞地尋找解決問題的答案時，我都會看到它。嘲弄我。 Stack Overflow。

無論如何，一些地獄般的影響使我試圖解決河內的塔。我的第一個解決方案是不完整的，因爲它導致了memory error如果有太多的磁盤上運行：

(define hanoi 
    (lambda (n from to other) 
    (cond ((< n 0) 
     (error `(Error! Number of disks ,n cannot be less than 0!))) 
     ((= n 0) 
     '()) 
     (else 
     (append (hanoi (- n 1) 
       from 
       other 
       to) 
      `((,from ,to)) 
      (hanoi (- n 1) 
       other 
       to 
       from)))))) 

我讀的地方，延續傳遞風格，將解決這個問題。然而，這didn't help either：

(define hanoi_cps 
    (lambda (n from to other c) 
    (cond ((< n 0) 
     (error `(Error! Number of disks ,n cannot be less than 0!))) 
     ((= n 0) 
     (c '())) 
     (else 
     (hanoi_cps (- n 1) 
       from 
       other 
       to 
       (lambda (x) 
      ((lambda (w) 
       (w `((,from ,to)))) 
      (lambda (y) 
       (hanoi_cps (- n 1) 
         other 
         to 
         from 
         (lambda (z) 
        (c (append x y z)))))))))))) 

Answer 1

繼續傳遞樣式，而不是通過遞歸調用來擴展堆棧空間，而是在環境中構建遞歸定義的lambda表達式，以便執行連續操作......換句話說，內存在某處沿線。例如，用一個簡單的階乘的算法，你通常會寫類似：

(define (factorial x) 
    (cond ((eq? x 0) 1)) 
      ((eq? x 1) 1)) 
      (else (* x (factorial (- x 1)))))) 

有了這個遞歸定義爲factorial，堆棧空間將被用完來保存參數到遞延乘法操作peformed每次遞歸函數調用。同樣功能的延續傳遞版本會是什麼樣子：

(define (factorial x cont) 
    (cond ((eq? x 0) (cont 1)) 
      ((eq? x 1) (cont 1)) 
      (else (factorial (- x 1) (lambda (y) (cont (* x y))))))) 

什麼會消耗堆棧空間之前，現在由匿名拉姆達的環境中使用了。在這種情況下，lambda的環境正在填充所需的值，以便通過每次遞歸調用factorial來解決x和cont的值。由於cont本身是一個具有環境的lambda，所以您可以看到內存將如何最終消耗，因爲每個lambda連續需要在其環境中將前一個調用的lambda存儲爲factorial ...這會創建一個遞歸定義的lambda連續它的環境基本上是通過遞歸調用factorial而得到的所有延續的遞歸列表。

查看延續傳遞風格的一種方式是，雖然基本上已經將函數調用機制轉換爲尾遞歸方法，但延續本身的實際定義本質上是遞歸的，所以您不會真正消除了算法的遞歸性質...換句話說，評估一個在尾遞歸調用上構建的延續需要在它內部計算一個遞歸定義的延續，它本身在其內部具有另一個遞歸定義的延續，等等。lambda-continuation的環境最終看起來就像是list-of-a-list-list-of-a-list等等。在lambda-continuation的環境中存儲所有這些遞歸定義需要內存，所以無論你是通過正常的遞歸調用約定消耗棧中的空間，或者通過存儲遞歸定義來消耗內存空間每個lambda延續中的環境，無論哪種方式，你最終都會耗盡空間。

Answer 2

CPS不會幫助你使事情變得更加內存效率，因爲通過執行它，你只是更換堆棧幀，匿名函數。如果您希望程序使用較少的內存，請嘗試回溯搜索（但請注意，您必須小心以避免無限移動序列）。