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函数，该函数将采用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和和。所以看起来像这样：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 回答