递归与迭代

递归的思路

1. 考虑一个最简单的例子。
2. 考虑一个改进 (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