树形递归

Author Avatar
WincerChan 7月 16, 2017
  • 在其它设备中阅读本文章

树形递归

与上一篇介绍的「线性递归」类似的另一种常见计算模式为「树形递归」。本质嘛,可以看作许多分支的线性递归。

还是直接上具体的例题。

「斐波那契数列^1」的定义如下v

看到这个定义我们马上就能把它编写成程序:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

这个程序完全就是按照定义来的,定义怎么说我就怎么写,不需要什么额外的思考。

来分析一下,如果我们需要计算 (fib 5),就需要计算出 (fib 4)(fib 3)。而为了计算 (fib 4),又需要计算出 (fib 3)(fib 2)。将这一过程展开后会像一棵数,如下图所示。这里的每一层都分裂为两个分支(除了最下面),也就是说对 fib 函数的每个调用中都包含了两次调用自身。

fib

这是一个很经典的树形递归的例子,但是它的计算效率太低了,做了太多的冗余计算。在图中求 (fib 3) 这个过程重复了 2 次。或者更明白的说:Fib(n) 值的增长对于 n 是指数的。Fib(n) 是最接近 $\phi^n/\sqrt5$ 的整数,其中 $\phi$ 满足 $\phi^2=\phi+1$,证明过程见这里

也就是说这个 Fib(n) 计算过程随着输入 n 的增长而指数性增长。而空间需求是线性增长,为什么呢?因为在计算中的每一点,我们只需要保存树中在此之上节点的轨迹。具体的,当我们所处的位置是 Fib(3) 的时候,只需要保存的轨迹是如何到达 Fib(3) 的就行了,至于后续是如何的,那不是当前 Fib(3) 所需要考虑的。

一般说,树形递归计算过程所需的步骤数正比于树中的结点数,其空间需求正比于数的最大深度。

迭代转化

我们当然可以规划一种迭代计算过程来计算「斐波那契数列」,基本想法是用一对整数 $a$ 和 $b$,将它们分别初始化为 Fib(1)=1Fib(0)=0,而后反复使用下面规则变换:

$a\longleftarrow a+b$

$b\longleftarrow a$

在应用了这些变换后,$a$ 和 $b$ 将分别等于 Fib(n+1)Fib(n)。因此,我们可以编成以下程序:

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

这种方法的计算步骤相对于 $n$ 来说是线性的,与上一个方法差距巨大。那么,到底有多大呢?我们编写一个程序测试:

(define (Fibo n start)
  (fib n)
  (- (real-time-clock) start))

;递归方法:(单位为ms)
1 ]=> (Fibo 30 (real-time-clock))
;Value: 1214

1 ]=> (Fibo 31 (real-time-clock))
;Value: 1735

1 ]=> (Fibo 32 (real-time-clock))
;Value: 2793

;迭代方法:
1 ]=> (Fibo 1000 (real-time-clock))
;Value: 1

1 ]=> (Fibo 5000 (real-time-clock))
;Value: 6

1 ]=> (Fibo 10000 (real-time-clock))
;Value: 13

当然这个并不严谨,实际的算法分析还是要根据数学公式推导、证明,但足以让我们感受到这二者方法的 天差地别。

当然也不能说树形递归计算过程根本没有用。因为树形递归计算过程可以帮助我们理解和设计程序。以「斐波那契数列」为例,虽然第一个方法远比第二个低效,但却更加直截了当,基本就是把定义翻译成了 Lisp 语言。

本文系本人阅读 SICP 时所做的笔记,全部笔记可在标签 SICP 中查看

本文标题: 树形递归
最后更新:2017 年 12 月 24 日 - 17:12
本文链接:https://blog.itswincer.com/posts/99a81f4c/
本文采用:署名-非商业性使用-禁止演绎 4.0 国际 协议进行许可,阅读 相关说明