這可以變成一個尾遞歸函數嗎？

Question

通過HtDP並遇到一個問題是：設計功能繁多。它消耗一個自然數n並將其乘以某個任意數x而不使用*。

這是我想出了：

(define (multiply n x) 
    (cond 
    [(= x 1) n] 
    [else (+ n (multiply n (- x 1)))])) 

它的工作原理，但我想，這是不是最好的解決方案。由於這可以作爲for循環解決，根據我的理解，這應該是尾遞歸的。

Answer 1

的尾遞歸解決方案的關鍵點：保持一個不變的N * X + R =常數。在這種情況下，當x是零時，r包含n * x。

(define (iter-mul n x r) 
    (cond ((= x 0) r) 
     (else (iter-mul n (- x 1) (+ r n))))) 

可以使用它作爲：

(define (mul n x) (iter-mul n x 0)) 

Answer 2

可能不是最優雅，但這是至少尾遞歸：

(define (acc a n x) 
    (if(= x 0) 
    a 
    (acc (+ a n) n (- x 1)))) 

(define (multiply n x) 
    (acc 0 n x)) 

Answer 3

該過程可以通過使用累加器參數用於存儲結果可以容易地轉換成尾遞歸。以下定義爲n >= 0和x >= 0，並且我正在使用名爲let（loop是一個尾遞歸過程，而不是循環構造）以避免需要顯式定義輔助過程或向過程添加另一個參數。以下是如何做到這一點：

(define (multiply n x) 
    (let loop ((acc 0) 
      (x x)) 
    (cond 
     [(= x 0) acc] 
     [else (loop (+ n acc) (- x 1))]))) 

還要注意的是你有一個錯誤在你的代碼，嘗試運行(multiply 1 0) - 一個無限循環。

Answer 4

現在其他人已經告訴你如何做一個函數尾遞歸，下面是一個函數的替代版本，它乘以兩個正整數，比你給出的要快得多。你看到這個功能是如何工作的嗎？

(define (times x y) 
    (let loop ((x x) (y y) (z 0)) 
    (if (zero? x) z 
     (loop (quotient x 2) (+ y y) 
      (if (odd? x) (+ y z) z)))))