在方案中創建一個尾遞歸功能函數

Question

我在想如何在方案中實現尾部回饋函數功能？

我有我的方案定義遞歸之一：

(define power-is-fun 
    (lambda (x y) 
    (cond [(= y 0) 
      1] 
      [(> y 0) 
      (* (power-is-fun x (- y 1)) x)]))) 

但我不能完全弄清楚另一個是如何應該是。

Answer 1

答案是相似的，你只需要積累的結果作爲參數傳遞：

(define power-is-fun 
    (lambda (x y acc) 
    (cond [(= y 0) 
      acc] 
      [(> y 0) 
      (power-is-fun x (- y 1) (* x acc))]))) 

這樣稱呼它，請注意，對於acc初始值是1（你可以建立一個輔助函數這一點，所以你不必記得每次）通過1：

(power-is-fun 2 3 1) 
> 8 

一些一般的指針改造遞歸過程爲尾遞歸：

• 添加一個額外的參數給函數舉行迄今已累計
• 結果傳遞的初始值累加器你第一次調用過程，通常這是你會在已經返回的值相同基本情況下的「正常」（非尾遞歸）遞歸。
• 在遞歸
• 的基本情況返回累加器在遞歸步驟，用一個新值更新累積的結果，並把它傳遞給遞歸調用
• 而最重要的是：在時機成熟時調用遞歸，確保將其稱爲最後一個表達式，不需要執行「額外工作」。例如，在你原來的代碼，你調用power-is-fun後進行乘法，而在尾遞歸版本，調用power-is-fun是退出程序

Answer 2

奧斯卡的建議名單是之前發生的最後一件事優秀。

如果你喜歡一個更深入的治療迭代（又名線性遞歸）和樹遞歸過程，那麼就不要錯過偉大的治療SICP：

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

Answer 3

順便說一句，有一個更快的方法來實現整數求冪。而不是一遍一遍乘以x，y倍（這使得O（Y）），還有一個辦法，是O的時間複雜度（日誌Y）：

(define (integer-expt x y) 
    (do ((x x (* x x)) 
     (y y (quotient y 2)) 
     (r 1 (if (odd? y) (* r x) r))) 
     ((zero? y) r))) 

如果你不喜歡do（儘可能多的陰謀家我知道這樣做），這裏有一個版本，尾遞歸明確（你也可以把它寫一個名爲let過，當然）：

(define (integer-expt x y) 
    (define (inner x y r) 
    (if (zero? y) r 
     (inner (* x x) 
       (quotient y 2) 
       (if (odd? y) (* r x) r)))) 
    (inner x y 1)) 

（什麼像樣的方案實施應宏展開這兩個版本完全同樣的代碼，另外，就像Óscar的解決方案一樣，我只使用累加器我稱之爲r（「結果」）。）