如何提高这段代码？

Question

我的解决办法来锻炼SICP 1.11 是：

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

如所预期的，一个评价如（F 100）需要较长的时间。我想知道是否有改善这种代码（没有前述递归）的方式，和/或利用多芯盒。我使用 'MIT-方案'。

Answer 1

我不知道如何以最佳方式是在方案代号，而是要改善这样的速度的常用技术是使用的记忆化。概括地说，这个想法是缓存度f（p）的结果（可能为每一个P观察，或者可能是最后n个值），以便下次呼叫度f（p）时，所保存的结果被返回，而不是重新计算。一般来说，高速缓存将是从一个元组（表示输入参数），以返回类型的地图。

Answer 2

在锻炼告诉你写两个功能，一个“通过递归过程的手段”计算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仍然是一个递归的功能但由于方案的工作方式，它会作为一个迭代的进程并运行在O(n)时间和O(1)空间，不像你代码这不仅是一个递归函数，但一个递归过程。我相信这是练习1.1的作者所期待的。

Answer 3

好了，如果你问我，觉得像一个数学家。我不能阅读计划，但如果你正在编写一个斐波那契数函数，而不是递归定义它，解决了复发，并用封闭的形式定义它。对于斐波纳契数列中，闭合形式可以发现此处例如。那会快很多。

编辑：哎呀，没看到你说放弃摆脱递归。在这种情况下，你的选择是非常有限的。

Answer 4

请参阅关于建立一个快速的斐波那契功能一个很好的教程这篇文章函数式编程。它采用Common Lisp的，这是计划在某些方面略有不同，但你应该能够用它获得通过。您的实施等效于靠近该文件的顶部的bogo-fig功能。

Answer 5

要换句话说：

要获得尾递归，递归调用必须是最后的事情过程的功能。

您递归调用嵌入*和+表达式中，所以它们不是尾调用（因为*和+被评估的之后递归调用。）

杰里米流转的的版本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)))

Answer 6

这特定锻炼可以通过使用尾递归来解决 - 而不是等待每个递归调用返回（如在简单的解决方案，你存在的情况下），则可以累积的答案中的参数，在这样的方式递归的行为完全一样，在它消耗了空间方面的迭代。例如：

(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)))