如何改进这段代码？

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-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的作者所寻求的.