我正在学习HtDP,遇到了一个问题: 设计函数multiply。它接受一个自然数n,并使用一些任意的数字x将其相乘,但不能使用*。
这是我想出来的:
(define (multiply n x)
(cond
[(= x 1) n]
[else (+ n (multiply n (- x 1)))]))
它能够工作,但我认为它并不是最好的解决方案。基于我的理解,这可以通过for循环来解决,应该是尾递归。
我正在学习HtDP,遇到了一个问题: 设计函数multiply。它接受一个自然数n,并使用一些任意的数字x将其相乘,但不能使用*。
这是我想出来的:
(define (multiply n x)
(cond
[(= x 1) n]
[else (+ n (multiply n (- x 1)))]))
它能够工作,但我认为它并不是最好的解决方案。基于我的理解,这可以通过for循环来解决,应该是尾递归。
(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
和 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)
- 这将导致无限循环。