方案中的尾遞歸功能函數

Question

我在寫方案中的尾遞歸函數函數時遇到了困難。我想用輔助函數編寫函數。我知道我需要一個參數來保存一個累計值，但之後我就陷入了困境。我的代碼如下。

(define (pow-tr a b) 
(define (pow-tr-h result) 
    (if (= b 0) 
    result 
    pow-tr a (- b 1))(* result a)) pow-tr-h 1) 

我編輯了我的代碼，現在它工作。它如下：

(define (pow-tr2 a b) 
(define (pow-tr2-h a b result) 
    (if (= 0 b) 
    result 
    (pow-tr2-h a (- b 1) (* result a)))) 
(pow-tr2-h a b 1)) 

有人可以向我解釋爲什麼輔助函數應該有與主函數相同的參數。我很難想出爲什麼這是必要的。

Answer 1

聲明「輔助函數應該具有與主函數相同的參數」是不正確的。您只需要在每次迭代中傳遞參數更改 - 例如，指數和累計結果。舉例來說，這將很好地工作，而沒有經過基地作爲參數：

(define (pow-tr2 a b) 
    (define (pow-tr2-h b result) 
    (if (= b 0) 
     result 
     (pow-tr2-h (- b 1) (* result a)))) 
    (pow-tr2-h b 1)) 

它的工作原理，因爲內，助手程序可以「看到」外，主要的過程中定義的參數a。而且由於基地永遠不會改變，我們不必傳遞它。要了解更多信息，請參閱精彩的SICP書中的標題爲「內部定義和塊結構」的部分。

既然你正在使用幫手程序，那麼開始使用named let是一個好主意，這是一種非常方便的編寫幫助程序的語法，而不需要明確編碼內部程序。以上代碼等同於：

(define (pow-tr2 a b) 
    (let pow-tr2-h [(b b) (result 1)] 
    (if (= b 0) 
     result 
     (pow-tr2-h (- b 1) (* result a))))) 

Answer 2

即使它具有相同的名稱，它也不是相同的參數。如果你深入瞭解口譯員的工作，你會看到「a」定義兩次。一次爲本地範圍，但它仍記得外部範圍的「a」。當解釋器調用一個函數時，它會嘗試將參數的值綁定到形式參數。

您通過像algol家族語言那樣的相當突變的狀態來傳遞值的原因是，通過不改變狀態，您可以使用替代模型來推斷過程的行爲。在任何時候使用參數調用的相同過程將會產生與使用相同參數從別處調用相同的結果。

在純粹的功能性風格中，值永遠不會改變，而是一直用新的值調用函數。編譯器應該能夠在緊密循環中編寫代碼，以更新堆棧中的值（尾部調用消除）。通過這種方式，您可以更多地關注算法的正確性，而不是擔當人工編譯器的角色，而實際上被告知這是一種非常低效的機器任務配對。