递归和迭代（Scheme描述）

可以毫不夸张的说，递归（Recursion）之于程序语言，已是最接近的本质的东西。 高级语言的代码进入编译器或解释器之前，必须解析（parse）成一种叫抽象语法树（AST）的数据结构。在数据结构的遍历、搜索、排序等操作中，递归函数随处可见。
有很多人对递归的理解非常教条，比如“迭代比递归的效率高”、“递归次数多了会爆栈”等种种论断几乎已经称为了程序猿的“常识”。
实际上，递归在代码和运行上去理解，分别有两个完全不同的意思，递归程序(procedure)和递归过程(process)是完全不同的东西。
并非递归程序(procedure)就一定会爆栈，迭代过程(process)和递归过程(process)的时间复杂度往往是相同的。

约定：程序(procedure)指的是一个具体的函数，通常是函数式编程里的“纯函数”，而过程(process)指的是计算的流程。程序是过程的抽象，程序的求值表现为过程的顺序执行。将“程序”替换为“函数(function)”似乎更适合中文表达，但《SICP》原书及大量Lisp语言数据均采用procedure这一术语。

1. 递归程序（递归函数）

所谓递归程序，就是程序自己调用自己。简单的举个计算阶乘的栗子（栗子营养丰富），阶乘的数学定义如下：

$$n! = n \cdot (n-1) \cdot (n-2) \cdot \cdots \cdot 3 \cdot 2 \cdot 1$$

根据上式，可得以下映射：

$$n! = n \cdot [(n-1) \cdot (n-2) \cdot \cdots \cdot 3 \cdot 2 \cdot 1] = n \cdot (n-1)!$$

可见，$n!$能表示为$n$和$(n-1)!$的乘积。若计算阶乘的程序是一个通用函数factorial，则计算$n!$需要用不同的$n$来反复调用factorial函数本身。
用Scheme语言来描述递归过程是极自然的事，如下：

(define factorial                      ;定义factorial为
  (lambda (n)                          ; 一个单参数n的函数，其函数体为：
    (if (= n 1)                        ;   如果 n = 1
      1                                ;      返回 1, 否则
      (* n (factorial (- n 1))))))     ;      返回 n * factorial(n-1)

计算$5!$等价于对(factorial 5)求值，可用代换模型展开为：

(factorial 5)                         ;代换原则为在函数体内用值代替参数          
(* 5 (factorial 4))                   ;5 != 1， 代换if的false分支
(* 5 (* 4 (factorial 3)))             ;4 != 1， ...
(* 5 (* 4 (* 3 (factorial 2))))       ;3 != 1， ...
(* 5 (* 4 (* 3 (* 2 (factorial 1))))) ;2 != 1， ...
(* 5 (* 4 (* 3 (* 2 1))))             ;1 == 1， (factorial 1)代换为1
(* 5 (* 4 (* 3 2)))                   ;(* 2 1)代换为2
(* 5 (* 4 6))                         ;(* 3 2)代换为6
(* 5 24)                              ;(* 4 6)代换为24
120                                   ;(* 5 24) => 120

不同编程语言实现的factorial函数可能语法上大相径庭，但表现的计算逻辑是完全一致的。

2. 线性递归过程和线性迭代过程

考察对(factorial n)的求值，n每增加1，代换展开的语句纵向会增加两层，这表示其时间复杂度是$O(n)$的。 同时，代换模型最长一行的“长度”也会增加1，这表示在程序运行时，栈空间的消耗也会增加1。换成专业的说法，此过程的空间复杂度也是$O(n)$的。

PS:你可别给我搞$O(2n)$这种表示法。：)

人们把$O(n)$的复杂度称为线性复杂度，所以递归函数factorial的求值是一个线性递归过程（Linear Recursive Process）。
很容易可以推论出线性递归过程的缺点，当$n$达到一定程度时，计算机的栈空间会被用完。然后悲剧的爆栈，轻则郁闷不已，重则机毁人亡。所以递归程序写起来爽（直接对数学事实的描述），执行起来“可能”会很要命。
但为什么要把“可能”两个字加上引号呢？因为阶乘还有另一个递归写法（注意：这里的“递归”是递归程序或递归函数）。
如果直接从过程考虑$n \cdot (n-1)!$这一数学表达式，把每个(factorial n)的值用一个变量$p$表示以避免栈开销。倒序执行以上过程，可以得到这样的数学表达：

$$\begin{gather}   c := 1,p := 1  \\   c := c+1,p:=c \cdot p=2\cdot1  \\    c := c+1,p:=c \cdot p=3\cdot2 \\ c := c+1,p:=c \cdot p=4\cdot6 \\ \cdots \end{gather}$$

以上的$:=$符号表示赋值，函数式编程的拥趸一看就会皱眉头，生怕带来副作用。那么我们避免使用Scheme语言的赋值（set!）语句，直接用递归函数实现如下:

(define iter          ;定义iter为
  (lambda (p c max)   ;  一个三参数p, c, max的函数 函数体为
   (if (> c max)      ;    如果c > max 则
     p                ;      返回 p， 否则
     (iter (* c p)    ;      递归调用iter，参数为: p * c
           (+ c 1)    ;                        c + 1
           max))))    ;                        max

(define factorial-2   ;定义factorial-2为
  (lambda (n)         ;  一个单参n的函数  函数体为
    (iter 1 1 n)))    ;    返回（iter 1 1 n)的求值结果

以上我们定义了求阶乘的factorial-2函数，它的本体是一个递归程序iter，对(factorial-2 5)求值等价于对(iter 1 1 5)求值，其代换模型如下：

(factorial-2 5)  ;factorial-2的函数体中把n代换为5 =>
(iter 1 1 5)     ;c=1, max=5, 1 < 5, 代换false分支 =>
(iter 1 2 5)     ;            2 < 5, 代换false分支 =>     
(iter 2 3 5)     ;  ...
(iter 6 4 5)     ;
(iter 24 5 5)    ;
(iter 120 6 5)   ;c=6, max=5, 6 > 5， 代换true分支，返回p
120

当然以上所有代换模型均是简化版本，我们省略了所有(iter p c max)中每个参数的数学表达式的求值代换，它们都需要栈空间。但无论如何，栈调用最多4个，(factorial-2 5)求值过程的空间复杂度为常数。
这种线性时间复杂度，常数空间复杂度的顺序计算过程称为线性迭代过程(Linear Iterative Process)。
习惯写如下C语言代码的人会认为(iter p c max)没有C语言的循环语句高效：

int fact(int n) {
    int p = 1;
    for(int c = 1; c <= n; ++c) {
        p = p * c;
    }
    return p;
}

但实际上for循环里的++c和p*c实际上也是函数的栈调用，此代码和Scheme语言的iter函数执行效率是相同的。

小贴士：背诵++i和i++哪个效率高，且大谈效率优化的C程序猿可以洗洗睡了，这个循环你无论用何种自增写法，现代C编译器生成的汇编代码都一样。++i和i++这种奇葩的语法本来就不应该存在于世间。除了让你记住一些没用的“知识”并乐此不疲以外，它们唯一的功能可能就是对写C语言编译器的“大师”们执行天诛，f**k their brains， yeah！

3. 尾递归实现（tail-recursive implementation)

以下文字翻译自《SICP》的第1.2.1节，因水平有限，可能不太准确：

造成对递归函数和递归过程之间混淆的一个原因是，大多数通用语言的实现（包括Ada，Pascal和C）的设计方式都使得任何递归函数的执行都会消耗大量内存，即便该递归函数描述的是一个迭代过程。这些语言只能通过特殊的“循环语句”来描述迭代过程，例如do、repeat、for和while等。本书第5章考虑的Scheme实现不存在此缺陷。即使迭代过程由递归函数描述，它也会以常数空间复杂度执行，称为尾递归。通过尾递归实现，可以使用递归函数来表示迭代过程，其它语言的“循环语句”在描述迭代过程时仅仅是一种语法糖。

尾递归的意思即Scheme语言的现代实现（chez scheme）如能够自动的把factorial函数转换为其尾递归版本解释或编译执行。
比较factorial函数和factorial-2函数，在知道阶乘的$n!=n \cdot (n-1)!$数学定义时，factorial的写法是最自然且语法最简的，factorial-2则不那么直观。自动尾递归优化能让我们无需考虑递归过程的空间复杂度，用最舒服的方式表现算法。
什么叫做尾递归呢？当一个函数的返回值为另一个函数的调用时，可称其为尾调用（tail-call），如果一个尾调用是递归的，则称为尾递归。参考以下代码：

(define func-1                   ;这是一个尾调用
  (lambda (n)                    ;返回值调用了*这个函数
    (* n 2)))                    ;
                                 ;  
(define func-2                   ;这不是一个尾调用     
  (lambda (x)                    ;返回值是一个值
    x))                          ;
                                 ;
(define func-3                   ;当n！=1时此函数即是
  (lambda (n)                    ;尾调用，又是尾递归
    (if (= n 1)                  ;它的返回值是自己的尾调用
      1                          ;
      (func-3 (- n 1)))))        ;
                                 ;
(define func-4                   ;这不是一个尾递归
  (lambda (n)                    ;返回值无论如何都不是尾调用自身
    (if (= n 1)                  ;
      1                          ;
      (* n (func-3 (- n 1))))))  ;

明显可以可以看出factorial-2里的递归函数iter是尾递归。尾递归只在栈空间改变形参，而不扩大表达式，因此不增加空间复杂度。
当然，不是所有的递归函数都能写成迭代过程，也就是说并非所有算法都能写成尾递归。若一个递归过程存在迭代形式，Scheme编译器会自动进行尾递归优化。
factorial函数和其尾递归优化后的代码如下：

;;递归过程原版 (* n (fact.... 这个操作会不断增加栈空间
(define factorial                   
  (lambda (n)                     
    (if (= n 1)                      
      1                                
      (* n (factorial (- n 1))))))

;;Scheme解释器或编译器的自动尾递归优化后的运行时函数    
(define tail-factorial
  (lambda (n tmp)
    (if (= n 1)
      tmp
      (tail-factorial (- n 1) (* n tmp)))))   

(define factorial
  (lambda (n)
    (tail-factorial 5 1)))

以上代码我未写注释，有兴趣的读者可用代换模型手算一下尾递归版本的factorial过程，以助理解。
Agian！通过代换模型，我们可以发现Lisp语言的这种(func arg1 arg2 arg3)的函数调用表现方式（s表达式）是“坠吼”的，它能直接以代换模型的“形状”来表达“迭代”和“递归”两种过程。这是其它语言的语法无法达到的设计高度。
用C语言语法去解释尾递归为什么空间复杂度为常数，实在是不够优雅和直接。

4. 总结

递归函数（function）或者说递归程序（procedure）是一种代码组织方法，它是非常自然的算法表达方式。
线性递归过程（process)和线性迭代过程（process）的时间复杂度都是$O(n)$，但是递归过程的空间复杂度也是$O(n)$，有爆栈风险。
尾递归函数是迭代过程。Scheme语言的实现能够自动尾递归优化，鼓励程序猿直接写递归程序，快速、自然且优雅的表达算法。
不要死记硬背迭代和递归的C语言版本定义，完全没说到点子上。如果有人告诉你递归比迭代慢，递归要爆栈，记得要微微一笑，绝对不抽（赵本山等，20xx）。