我將如何去做這個尾遞歸？

Question

我有這樣的代碼：

(define (prog1 x y) 
    (let ([rel (related x y)]) 
     (cond 
     [(null? rel) (list x)] 
     [else (cons x (map (lambda (d) (prog1 (neighbour d) y)) rel))]))) 

我想要做的是試圖使它尾遞歸。我知道，我需要做的是這樣的：

(define (prog1 x y) 
    (prog1-iter x y `())) 

(define (prog1-iter x y acc) 
    (... 
    )) 

但我不確定如何從我的代碼這個代碼去...我認爲這是因爲原中有一張地圖，而且我不確定如何將其併入prog1-iter。有人能指出我正確的方向！

Answer 1

尾遞歸很容易爲固有迭代的事物編寫。你的函數可能多次調用自己，所以它不會很簡單。儘管如此，任何程序都可以迭代（例如，您的計算機是一個巨大的迭代機器），因此可以完成。

首先，您的功能不是直接遞歸（即prog1不直接調用自己）。相反，prog1調用map，然後調用您給它的lambda（可能多次），然後調用prog1;所以它是間接的。撥打map不是一個尾巴呼叫;從map到lambda的呼叫肯定不是尾巴呼叫（它可能需要多次呼叫）;並且從lambda到prog1的呼叫是尾部呼叫。

因此，我不確定當你要求它是「尾遞歸」時你究竟需要什麼。您是否希望prog1的呼叫鏈中的每個呼叫都能成爲尾呼？或者你想讓程序中的每個通話都是通話？存在「尾遞歸」的map版本，但他們只是「尾遞歸對於呼叫從map到map，而不是映射函數調用，所以它們不是你的情況下非常有用。

的通常的方法是讓程序中的每個調用都進行一次尾部調用，稱爲continuation-passing style。基本上，每個函數都需要一個附加的函數參數，即「continuation」，而不是對函數進行非尾部調用，而是對尾部調用它繼續傳遞一個繼續，指定如何處理函數調用的結果，基本上，延續將包含非尾調用後原始函數的「其餘部分」，並且它將在「返回結果」中原始的非尾部呼叫作爲參數，我將把它作爲練習如何轉換y我們的CPS計劃。