SICP学习笔记之二

3. 递归
3.1 什么是递归

定义一个过程，需要三要素：过程名称、需要的参数，过程体。过程体，具体描述了此过程是做什么的，在过程体中，可以引用其他定义好的过程。

如果一个过程，在过程体中引用了自身，就说此过程是递归的。看例子：

(define (p) (p))

对照过程三要素，第一个(p)，表示此过程的名称是p，此过程不需要参数，第二个(p)，是过程体，也是一个表达式，表示此过程要做的事情，就是调用过程p。最后一句容易头晕，先运行一下过程。

(p)

结果如图所示。

注意右下角的小人，一直在弯腰奔跑，表明此过程一直在执行。不用继续等待了，这么简单的一个定义，居然是无穷循环。只能借助右上角的“停止”功能，强行中断。

仔细体会一下：定义了一个过程p，此过程不需要参数，此过程干什么呢，此过程要调用过程p。似曾相识吧，从前有座山、山里有座庙、庙里有个老和尚、老和尚在讲故事、讲什么呢，讲的是从前有座山…

(define (p) (p))，一个p引发的老和尚讲故事的故事。一直有个疑惑，为什么这个美丽而又深刻的故事，没有刻在某个计算机科学学院的徽标上呢^_^

其实递归本身还是比较费解的。在过程还没有定义完全的时候，就被引用，还要被引用的引用所引用，以至于无穷。很自然的想法是，在某种条件下，这种嵌套的引用，总应该有个终点吧。

下面先来看Schema如何描述条件的。

3.2 条件表达式

Schema的条件表达式也很简洁，先看if表达式的定义。

(if <条件表达式> 
<条件为真，执行此表达式>
<条件为假，执行此表达式>)

看看如何求某个数的绝对值。

(define (abs x) 
    (if (< x 0)
        (- x)
         x))

(abs -10)
10

(abs 10)
10

其中，表达式(< x 0)判断x是否小于0。没有了else的if，用起来还是很清爽的。条件表达式可以组合使用。

(and (> x 5) (< x 10))

表示 5 < x < 10，遇到类似的组合，望文生义就可以了。另外还有一个分支条件表达式cond比较常用，还是求某个数的绝对值。

(define (cond-abs x)
  (cond
    ((> x 0) x)
    ((= x 0) 0)
    ((< x 0) (- x))
    )
  )

(cond-abs -10)
10

和常用的switch/case语法类似，就不多说了。

3.3 线性递归

讲编程总是从“Hello,World”开始，讲递归也总是从阶乘开始。数n的阶乘为

 n! = n*(n-1)…3*2*1

此过程的定义并不难。

(

define (factorial n) 
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

计算数4阶乘的实际过程为。

(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 (* 1 (factorial 0)))))
(* 4 (* 3 (* 2 (* 1 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

从形状上看，是先逐步展开而后逐步收缩，真正的计算过程，是从收缩时开始的。用SICP中的原话，“这一计算过程构造起一个推迟进行的操作所形成的链条”(裘宗燕老师的译文)。数n越大，这个链条就越长，在计算过程真正开始前，需要保留的信息也就越多。这种计算过程，就是一个线性递归过程。

3.4 线性迭代

线性递归过程和人们的日常思维方式接近，下面用另外一种方法来计算数的阶乘。

(define (factorial-iteration n)
  (iteration 1 1 n))

(define (iteration result i n )
  (if (> i n)
      result
      (iteration (* i result)
                 (+ i 1)
                 n)))

(factorial-iteration 4)
24

在计算某个数的阶乘时，另外引入了有3个参数的新过程。看起来有点突然，把阶乘公式反过来写就容易理解了。

n! = 1*2*3…(n-1)*n

求n的阶乘，先计算1*2，得到结果2，然后看看n是否为2，不是的话，再把结果乘以3，得到结果6，然后看看n是否为3，以此类推。计算数4阶乘的实际过程为。

(factorial-iteration 4)
(iteration  1 1 4)
(iteration  1 2 4)
(iteration  2 3 4)
(iteration  6 4 4)
(iteration 24 5 4)
24

从形状上看，此过程没有任何曲线，脖子和腰身那是一桶到底。而且，给定任何一个中间状态，比如(iteration  24 5 6)，就可以知道以下信息：要计算6的阶乘，当前算到第5步，中间结果为24。根据迭代规则可以确定，只要再继续迭代2步，就能得到最后结果。这种计算过程，就是一个线性迭代过程。

需要注意，递归过程和递归计算过程是不一样的。递归过程，指的是在定义过程时引用了自身；递归计算过程，指的是具体的实现方式。这种区别容易意会，不易言传，分辨不清也没什么关系。

3.5 树形递归

对于熟悉的斐波那契数列：

0, 1, 1, 2, 3, 5, 8, 13,…

对应的递归过程为。

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

(fib 5)
5

将计算展开来看很像一棵树，这种计算过程，就是一个树形递归过程。

树形递归过程很直观，但是计算效率比较低。

评论

2 楼 gordonAtJava 2009-08-24  

就是一般递归和尾递归，因为尾递归程序里面的上下文都保存在一个变量里面，最终直接把结果返回，不需要堆的信息保存，所以在每次递归调用时都可以把外面的调用stack扔掉，这个在编译器层面可以直接优化为跳转（等同循环），而不是递归。
树递归没办法优化为循环，因为stack要保存上下文，不过某些树递归式可以通过动态规划来提高效率，有些是可以优化为尾递归的，比如你上面最后一个fib的例子。

1 楼 topman 2009-06-14  

Thanks again.