直接将书本给出的定义『如果 \(n < 3\) 那么 \(f(n) = n\) ;如果 \(n \geq 3\) ,那么 \(f(n)=f(n-1) + 2f(n-2) + 3f(n-3)\) 』翻译成递归函数:
;;; 11-rec.scm
(define (f n)
(if (< n 3)
n
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
测试这个递归版的 f
:
1 ]=> (load "11-rec.scm")
;Loading "11-rec.scm"... done
;Value: f
1 ]=> (f 1)
;Value: 1
1 ]=> (f 3)
;Value: 4
1 ]=> (f 4)
;Value: 11
要写出函数 \(f\) 的迭代版本,关键是在于看清初始条件和之后的计算进展之间的关系,就像书本 25-26 页中,将斐波那契函数从递归改成迭代那样。
根据函数 \(f\) 的初始条件『如果 \(n < 3\) ,那么 \(f(n)=n\) 』,有等式:
\(f(0) = 0\)
\(f(1) = 1\)
\(f(2) = 2\)
另一方面, 根据条件『当 \(n \geq 3\) 时,有 \(f(n) = f(n-1)+2f(n-2)+3f(n-3)\) 』,如果继续计算下去,一个有趣的结果就会显现出来:
\(f(3) = f(2) + 2f(1) + 3f(0)\)
\(f(4) = f(3) + 2f(2) + 3f(1)\)
\(f(5) = f(4) + 2f(3) + 3f(2)\)
\(\dots\)
可以看出,当 \(n \geq 3\) 时,所有函数 \(f\) 的计算结果都可以用比当前 \(n\) 更小的三个 \(f\) 调用计算出来。
迭代版的函数定义如下:它使用 i
作为渐进下标, n
作为最大下标, a
、 b
和 c
三个变量分别代表函数调用 \(f(i+2)\) 、 \(f(i+1)\) 和 \(f(i)\) ,从 \(f(0)\) 开始,一步步计算出 \(f(n)\) :
;;; 11-iter.scm
(define (f n)
(f-iter 2 1 0 0 n))
(define (f-iter a b c i n)
(if (= i n)
c
(f-iter (+ a (* 2 b) (* 3 c)) ; new a
a ; new b
b ; new c
(+ i 1)
n)))
测试这个迭代版的函数:
1 ]=> (load "11-iter.scm")
;Loading "11-iter.scm"... done
;Value: f-iter
1 ]=> (f 1)
;Value: 1
1 ]=> (f 3)
;Value: 4
1 ]=> (f 4)
;Value: 11
两个 \(f\) 函数不仅使用的计算方式不同(前一个递归计算,另一个迭代计算),而且效率方面也有很大的不同。
递归版本的函数 \(f\) 有很多多余的计算,比如说,要计算 \(f(5)\) 就得计算 \(f(4)\) 、 \(f(3)\) 和 \(f(2)\) ,而计算 \(f(4)\) 又要计算 \(f(3)\) 、 \(f(2)\) 和 \(f(1)\) 。
对于每个 \(f(n)\) 调用,递归版 \(f\) 函数都要执行 \(f(n-1)\) 、 \(f(n-2)\) 和 \(f(n-3)\) ,而 \(f(n-1)\) 的计算又重复了对 \(f(n-2)\) 和 \(f(n-3)\) 的计算,因此,递归版本的 \(f\) 函数是一个指数级复杂度的算法(和递归版本的斐波那契数函数类似)。
另一方面,迭代版本使用三个变量储存 \(f(n-1)\) 、 \(f(n-2)\) 和 \(f(n-3)\) 的值,使用自底向上的计算方式进行计算,因此迭代版的函数 \(f\) 没有多余的重复计算工作,它的复杂度正比于 \(n\) ,是一个线性迭代函数。
See also
查看维基词条 Dynamic Programming 了解更多关于自底向上计算的信息。