通过 HtDP 并遇到一个问题是:设计函数乘法。它消耗一个自然数 n 并将其与某个任意数 x 相乘,而不使用 *。
这就是我想出的:
(define (multiply n x)
(cond
[(= x 1) n]
[else (+ n (multiply n (- x 1)))]))
它有效,但我认为这不是最好的解决方案。由于这可以作为 for 循环解决,根据我的理解,这应该是尾递归的。
通过 HtDP 并遇到一个问题是:设计函数乘法。它消耗一个自然数 n 并将其与某个任意数 x 相乘,而不使用 *。
这就是我想出的:
(define (multiply n x)
(cond
[(= x 1) n]
[else (+ n (multiply n (- x 1)))]))
它有效,但我认为这不是最好的解决方案。由于这可以作为 for 循环解决,根据我的理解,这应该是尾递归的。
尾递归解法的关键点:保持一个不变的 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))
既然其他人已经向您展示了如何使函数尾递归,这里是一个函数的替代版本,用于将两个正整数相乘,它比您给出的要快得多。你明白这个函数是如何工作的吗?
(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)))))
可能不是最优雅的,但这至少是尾递归的:
(define (acc a n x)
(if(= x 0)
a
(acc (+ a n) n (- x 1))))
(define (multiply n x)
(acc 0 n x))
通过使用用于存储结果的累加器参数,可以轻松地将过程转换为尾递归。以下是为n >= 0
and定义的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)
- 无限循环。