recursion - 如何改进这段代码？

Question

我对 exercise 1.11 的解决方案SICP 的内容是:

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

正如预期的那样，诸如 (f 100) 之类的评估需要很长时间。我想知道是否有一种方法可以改进此代码(无需放弃递归)和/或利用多核盒。我正在使用“mit-scheme”。

Answer 1

本练习要求您编写两个函数，其中一个计算 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 的作者所寻找的。