Scheme中的遞歸函數總是進行尾調優化？

Question

我讀過一些關於Scheme中tail-call優化的內容。但我不確定我是否理解尾部呼叫的概念。如果我有這樣的代碼：

(define (fac n) 
    (if (= n 0) 
     1 
     (* n (fac (- n 1))))) 

這可以優化，以便它不會採取堆棧內存？ 或可以尾部調用優化僅被施加到這樣的函數：

(define (factorial n) 
    (let fact ([i n] [acc 1]) 
     (if (zero? i) 
      acc 
      (fact (- i 1) (* acc i))))) 

Answer 1

考慮尾調用的一個有用的方法是詢問「遞歸過程調用的結果必須發生什麼？」

第一功能不能尾優化的，因爲內部呼叫的結果到fac必須使用，並乘以n以產生到fac整體呼叫的結果。

然而，在第二種情況下，對fact的「外部」呼叫的結果是......內部呼叫fact的結果。其他任何事情都不必做，而後者的值可以直接作爲函數的值傳回。這意味着不需要保留其他函數上下文，因此可以簡單地將其丟棄。

R5RS標準通過使用tail context的概念來定義「尾部呼叫」，這基本上就是我上面所描述的。

Answer 2

否，第一fac不能被優化。

當一個函數被調用時，您需要知道它被調用的位置，以便您可以在調用完成後返回到該位置，並在將來的計算中使用調用結果（函數fac）。

fact以不同方式實施。 fact所做的最後一件事就是自稱。沒有必要記住我們呼叫的地方 - 相反，我們可以執行尾部呼叫消除。 fact返回後不應執行其他操作。