递归的思路
- 考虑一个最简单的例子。
- 考虑一个改进 (improve) 过程，使其对任意的输入值，总是朝向 1 中的最简单的例子方向改进的。
递归的优点
一个人在见过如何通过递归解决汉诺塔问题或 counting change 问题之后，很难不产生某种惊喜感。是的，这就是递归的优点：它只考察最简单的例子和“半空中的”、局域的过程 (improve)。这两者都是相对而言非常容易的。
相比之下，迭代需要从“地基”一点一点地向空中行进，其中的每一步都需要考察清楚，相比于递归来说，这常常是艰难的。
递归的缺点
线性递归和树递归分别带来空间和时间上的指数增长。相比之下，线性迭代只带来时间上的线性增长。
然而，这通常是容易解决的。正如之前些计算 NG 的包时遇到的令人印象深刻的情况一样，只需要加几行代码，即做一点简单的优化，就可以使递归从指数变成线性的，甚至更好 (对数的)。例如，fast-expt。
迭代的缺点
显然，迭代很难看懂。相比于递归，它造成了不必要的理解的困难。然而，它的计算效率的优势相比于简单地改进了的递归来说并不占明显的、必要的优势。例如，比较
define (fast-expt b n)
(fast-expt-iter b n 1))
(define (fast-expt-iter b n a)
(if (= n 0)
a
(if (even? n)
(fast-expt-iter (* b b)
(/ n 2)
a)
(fast-expt-iter b
(- n 1)
(* a b)))))
与
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
是不是第一个看着很眼晕，而第二个 (by definition) 很显然？！
categories: programming
