3

我对 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'。

4

6 回答 6

8

该练习告诉您编写两个函数,一个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函数,该函数将采用ab、 和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,bc应该分别初始化为2, 1, 和0,这也遵循fib函数初始化的模式a和和。所以看起来像这样:b10f

(define (f n)
  (f-iter 2 1 0 n))

注意:f-iter仍然是一个递归函数,但由于 Scheme 的工作方式,它作为一个迭代过程运行并在O(n)时间和O(1)空间中运行,这与您的代码不同,它不仅是一个递归函数,而且是一个递归过程。我相信这就是练习 1.1 的作者所寻找的。

于 2009-04-21T04:24:23.630 回答
4

我不确定如何最好地在 Scheme 中对其进行编码,但是提高此类速度的常用技术是使用memoization。简而言之,这个想法是缓存 f(p) 的结果(可能是每个看到的 p,或者可能是最后 n 个值),以便下次调用 f(p) 时,返回保存的结果,而不是重新计算。通常,缓存是从元组(表示输入参数)到返回类型的映射。

于 2009-04-21T04:22:34.930 回答
2

好吧,如果您问我,请像数学家一样思考。我看不懂方案,但是如果您正在编写斐波那契函数,而不是递归地定义它,解决递归并用封闭形式定义它。例如,对于斐波那契数列,可以在此处找到封闭形式。那会快得多。

编辑:哎呀,没有看到你说放弃摆脱递归。在这种情况下,您的选择会更加有限。

于 2009-04-21T04:46:23.297 回答
1

有关使用函数式编程开发快速斐波那契函数的好教程,请参阅这篇文章。它使用Common LISP,在某些方面与Scheme略有不同,但您应该可以使用它。您的实现相当于bogo-fig文件顶部附近的函数。

于 2009-04-21T04:24:12.820 回答
0

换一种方式:

要获得尾递归,递归调用必须是过程所做的最后一件事。

您的递归调用嵌入在 * 和 + 表达式中,因此它们不是尾调用(因为 * 和 +在递归调用之后进行评估。)

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)))
于 2009-04-22T08:47:12.943 回答
0

该特定练习可以通过使用尾递归来解决 - 而不是等待每个递归调用返回(就像您提供的直接解决方案中的情况一样),您可以将答案累积在一个参数中,这样递归的行为就其消耗的空间而言,它与迭代完全相同。例如:

(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)))
于 2011-11-14T21:03:27.910 回答