递推式的迭代表达

Ma Kai posted @ Feb 28, 2016 01:44:50 PM in 编程 with tags Scheme SICP , 691 阅读

考虑 Fibonacci 数列:f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) (n=2, 3, 4, ...)

可以很轻松地写出其递归形式表达(这里使用 Racket):

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

很显然,这个函数是无法被尾递归优化的。但是我们也可以很简单地将它转化为线性迭代过程:

(define (fib-iter a b n)
  (if (= n 0)
      a
      (fib-iter b (+ a b) (- n 1))))
(define (fib n)
  (fib-iter 0 1 n))

这样做的原理是什么呢?实际上,我们只不过是把每次运算的结果丢弃掉,然后换上下一次需要的数据而已。比如说,我们要计算 f(n+1),那么就需要知道 f(n-1) 和 f(n)。循环的终止条件是 n=0,然后返回 a。如何验证这样做是正确的?可以列出如下表:

i=n     a=f(0)   b=f(1)
i=n-1   a=f(1)   b=f(2)
i=n-2   a=f(2)   b=f(3)
...
i=1     a=f(n-1) b=f(n)
i=0     a=f(n)   b=f(n+1)

我们得到了我们想要的结果 f(n)!循环终止条件不用 n=1 的理由是:如果一开始传入的 n 就是 0,那么循环将永远无法终止。而使用 n=1 所得到的效率优化微乎其微、可以忽略不计。

可以用完全相同的思路解决 SICP 练习 1.11:写出计算 f(n)=n (n<3), f(n)=f(n-1)+2f(n-2)+3f(n-3)(n>=3) 的递归和迭代的代码。

递归非常简单且自然:

(define (foo n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

使用相同的表格:

i=n    a=f(0)   b=f(1)   c=f(2)
i=n-1  a=f(1)   b=f(2)   c=f(3)
i=n-2  a=f(2)   b=f(3)   c=f(4)
...
i=0    a=f(n)   b=f(n+1) c=f(n+2)

可以帮助我们写出正确的迭代代码:

(define (foo-iter a b c count)
  (if (= count 0)
      c
      (foo-iter b c (+ (* 3 a) (* 2 b) c) (- count 1))))
(define (foo n)
  (foo-iter 0 1 2 n))

可以使用循环不变式证明该代码是正确的。

将以上结论推广,可以得到:

定义在 N 上的函数 f(n),对于 n>=N,有 f(n)=A1f(n-1)+A2f(n-2)+A3f(n-3)+...,其中 A1, A2, ... 都是常数,那么对于任意 n<N,f(n) 都是需要另行定义的。其递归伪代码必为如下格式:

(define (f n)
  (cond ((n=1) ...)
        ((n=1) ...)
        (...)
        ((n=N) ...)
        (else (+ (* A1 (f (- n 1))
                 (* A2 (f (- n 2))
                 ...))))

其迭代代码一定需要 N 个变量,必为如下格式:

(define (f-iter a b c d e ... count)
  (if (= count 0)
      a
      (f-iter b c d e ... (+ ...) (- count 1))))
(define (f n)
  (f-iter f0 f1 f2 ... fN n))

当 N 比较大时,可能 f(n+1), f(n+2), f(n+3), ..., f(n+N-1) 的计算成本就无法忽略了,这时我们可以在 f 里面想想办法。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter