这个函数能转换成尾递归函数吗？

Question

我正在学习HtDP，遇到了一个问题： 设计函数multiply。它接受一个自然数n，并使用一些任意的数字x将其相乘，但不能使用*。

这是我想出来的：

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

它能够工作，但我认为它并不是最好的解决方案。基于我的理解，这可以通过for循环来解决，应该是尾递归。

- dotnetN00b

Answer 1

尾递归解决方案的关键要点是：保持一个固定不变的不变量n * x + r = const。在这种情况下，当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))

- Dmitriy Kuznetsov

Answer 2

既然其他人已经向您展示了如何使函数成为尾递归，这里有一个用于将两个正整数相乘的替代版本，比您提供的函数快得多。您看到这个函数是如何工作的吗？

(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)))))

- user448810

Answer 3

今日免费次数已满, 请开通会员/明日再来

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

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

- Ryan Cavanaugh

Answer 4

通过使用累加器参数来存储结果，可以轻松将该过程转换为尾递归。对于 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) - 这将导致无限循环。

- Óscar López