爲什麼在方案的所有實現中都需要尾遞歸？

Question

尾遞歸效率更高，因爲它重用相同的堆棧幀而不是創建一個新的，但爲什麼這需要在方案中的所有內容？

Answer 1

尾遞歸由語言的規範來強制執行。從R6RS的5.11部分引用：

Scheme的實現必須是正確的尾遞歸。在某些稱爲尾部上下文的語法上下文中發生的過程調用是尾部調用。如果Scheme支持無限數量的活動尾部調用，則Scheme實現是正確的尾遞歸。如果被叫程序仍可能返回，則該呼叫處於活動狀態。請注意，這包括常規回報以及之前通過隨後調用的電流繼續捕獲的延續進行的返回。在沒有被捕獲延續的情況下，呼叫最多可以返回一次，而主動呼叫將是那些尚未返回的呼叫。在Clinger的論文[5]中可以找到正確的尾遞歸正式定義。第11.20節描述了從（rnrs base（6））庫中識別結構中尾部調用的規則。

實際的原因是，尾遞歸允許使用遞歸實現有效的循環。

Answer 2

Scheme沒有goto，所以所有循環最終都是使用尾遞歸完成的。如果沒有適當的尾部遞歸保證，在Scheme中沒有可靠的方法來提供循環。

---

更新：我想解釋一下我所說的「最終使用尾遞歸」。我們來看看do宏，因爲@newacct提到了它。例如：

(do ((i 1 (+ i 1))) 
    ((> i 10)) 
    (display i) 
    (newline)) 

正如我所說，方案沒有goto，所以它必須得到它從什麼地方循環。它實際上是宏觀擴展到（像）這樣的：

(let loop ((i 1)) 
    (unless (> i 10) 
    (display i) 
    (newline) 
    (loop (+ i 1)))) 

注意loop這裏不是關鍵字或內置函數。這是一個命名函數，它由名爲let^†創建，並且正在unless表單底部調用（通過尾遞歸）。

真的，Scheme中的所有標準循環形式都使用尾遞歸。有沒有擺脫它。

---

†這裏是名爲let（嚴格地講^‡）宏觀擴展爲：

(letrec ((loop (lambda (i) 
       (unless (> i 10) 
        (display i) 
        (newline) 
        (loop (+ i 1)))))) 
    (loop 1)) 

‡嚴格地說，它的宏觀擴展爲：

((letrec ((loop (lambda (i) 
        (unless (> i 10) 
        (display i) 
        (newline) 
        (loop (+ i 1)))))) 
    loop) 
1) 

Answer 3

沒有TR保證call/cc將無法​​使用。循環本身可以通過dowhich is a part of the language來實現。

編輯：原來這是不正確的。請參閱John Clements在該問題上的評論。一種語言可以具有非TR函數調用機制，但是具有用於調用繼續的特殊分離機制。