我对 SICP练习 1.11的解决方案是:
(define (f n)
(if (< n 3)
n
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
))
正如预期的那样,(f 100)之类的评估需要很长时间。我想知道是否有办法改进这段代码(不考虑递归),和/或利用多核盒子。我正在使用'mit-scheme'。
该练习告诉您编写两个函数,一个f
“通过递归过程”进行计算,另一个f
“通过迭代过程”进行计算。你做了递归的。由于此函数与您链接到的部分示例中给出的函数非常相似,因此fib
您应该能够通过查看函数的递归和迭代示例来弄清楚这一点fib
:
; Recursive
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
; Iterative
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
在这种情况下,您将定义一个f-iter
函数,该函数将采用a
、b
、 和c
参数以及count
参数。
这是f-iter
功能。注意与 的相似性fib-iter
:
(define (f-iter a b c count)
(if (= count 0)
c
(f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
并且通过一些尝试和错误,我发现a
,b
和c
应该分别初始化为2
, 1
, 和0
,这也遵循fib
函数初始化的模式a
和和。所以看起来像这样:b
1
0
f
(define (f n)
(f-iter 2 1 0 n))
注意:f-iter
仍然是一个递归函数,但由于 Scheme 的工作方式,它作为一个迭代过程运行并在O(n)
时间和O(1)
空间中运行,这与您的代码不同,它不仅是一个递归函数,而且是一个递归过程。我相信这就是练习 1.1 的作者所寻找的。
我不确定如何最好地在 Scheme 中对其进行编码,但是提高此类速度的常用技术是使用memoization。简而言之,这个想法是缓存 f(p) 的结果(可能是每个看到的 p,或者可能是最后 n 个值),以便下次调用 f(p) 时,返回保存的结果,而不是重新计算。通常,缓存是从元组(表示输入参数)到返回类型的映射。
好吧,如果您问我,请像数学家一样思考。我看不懂方案,但是如果您正在编写斐波那契函数,而不是递归地定义它,解决递归并用封闭形式定义它。例如,对于斐波那契数列,可以在此处找到封闭形式。那会快得多。
编辑:哎呀,没有看到你说放弃摆脱递归。在这种情况下,您的选择会更加有限。
有关使用函数式编程开发快速斐波那契函数的好教程,请参阅这篇文章。它使用Common LISP,在某些方面与Scheme略有不同,但您应该可以使用它。您的实现相当于bogo-fig
文件顶部附近的函数。
换一种方式:
要获得尾递归,递归调用必须是过程所做的最后一件事。
您的递归调用嵌入在 * 和 + 表达式中,因此它们不是尾调用(因为 * 和 +在递归调用之后进行评估。)
Jeremy Ruten 的版本f-iter
是尾递归而不是迭代(即它看起来像一个递归过程,但与迭代等效物一样有效。)
但是,您可以使迭代显式:
(define (f n)
(let iter
((a 2) (b 1) (c 0) (count n))
(if (<= count 0)
c
(iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
或者
(define (f n)
(do
((a 2 (+ a (* 2 b) (* 3 c)))
(b 1 a)
(c 0 b)
(count n (- count 1)))
((<= count 0) c)))
该特定练习可以通过使用尾递归来解决 - 而不是等待每个递归调用返回(就像您提供的直接解决方案中的情况一样),您可以将答案累积在一个参数中,这样递归的行为就其消耗的空间而言,它与迭代完全相同。例如:
(define (f n)
(define (iter a b c count)
(if (zero? count)
c
(iter (+ a (* 2 b) (* 3 c))
a
b
(- count 1))))
(if (< n 3)
n
(iter 2 1 0 n)))