对递归的理解

今天看了 SICP 上关于递归的一个讨论。明白了一个道理：

形式上是递归的不等于本质上也是递归的。

如果一个函数形式上是递归的，即他调用了自己。不等于这个函数在本质上是递归的，有可能这个函数在本质上是迭代的。

对于一个本质上是递归的函数，递归深度增加时，需要记录之前路径上所有的状态，也就是说内存的增长也是线性的。 对于一个本质上是迭代的函数，虽然形式上也是递归的，但是这种递归属于“尾递归”。这类函数，在递归深度增加时，本质上不需要内存也线性增长，而只需要固定数量的内存记录下当前的状态就行。这样实现的“尾递归”，其实就可以去除语言中所需要的 for, while 等用于迭代的语法糖。

但是，一些程序设计语言在实现时，会将所有递归都实现成内存随着递归深度增加而增长的形式。不过像 Scheme 这样的语言就不会这样实现。所以我们会听过函数式编程中，尾递归会以迭代的形式实现，递归深度增加时，不会爆栈。道理就在这里。

SICP 中使用了计算 n! 的两种方式来解释这个问题：

方法一：

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

factorial(6)
= 6 * factorial(5) 
= 6 * (5 * factorial(4) )
= ... = 6 * (5 * (4 * (3 * (2 * (factorial(1))))))
= 6 * (5 * (4 * (3 * (2 * (1)))))
= 6 * (5 * (4 * (3 * 2)))
= 6 * (5 * (4 * 6))
= 6 * (5 * 24)
= 6 * 120
= 720

从上面的代码及示例中可以看出，这个方法本质上是递归的，它需要记录从函数最上层到最底层路径上所有的状态，然后再反方向计算过去。

方法二：

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
    product
    (fact-iter  (* counter product)
                (+ counter 1))))  

factorial(6)
= fact-iter(1 1 6)
= fact-iter(1 2 6)
= fact-iter(2 3 6)
= fact-iter(6 4 6)
= fact-iter(24 5 6)
= fact-iter(120 6 6)
= fact-iter(720 7 6)

从上面的代码及示例中可以看出，这个方法本质上是迭代的，它只需要记录当前状态(product counter max-count) 就行，从前向后算，一直 到 counter 增加到 max-count 上为止。

对应到我们平时所用的非函数式语言，方法一其实是用递归实现，方法二是用 for 或者 while 迭代实现的，只不过在 Scheme 里，迭代也用递归的形式表达，但是解释器在实现时，本质上还是进行一个迭代的过程。