发布时间 : 星期一 文章递归和迭代 - 图文更新完毕开始阅读6e17b5ddc281e53a5902ff02
迭代是一个重复过程，它的目的是接近既定的目标或结果。每次重复的过程也称为”迭代“，作为迭代的结果都将作为下一次迭代的起点。
迭代在计算中是指的计算机程序中的重复的语句块。它可以表示两个专业术语，同义重复，以及描述一种具有可变状态重复的具体形式。然后令人费解的是，它也可以表示通过显式重复结构的任何重复，而不管其可变性。
在第一个意义上，递归是迭代的一个例子，但通常用”递归“来标记，而不作为”迭代“的例子。
在第二个意义上，（更加狭义地）迭代描述了一种编程风格。这与一个有着更有声明性方法的递归有着鲜明的对比。
第三个意义上，使用while或for循环，以及使用map或fold的函数也被视为迭代。
（以上定义部分摘自英文维基百科）
关于递归和尾递归在函数式编程中的应用也可以看这里：【Scheme归纳】3 比较do, let, loop
下面我也列出了相关的Scheme语言的代码：
(define (factorial n) (if (= n 1) 1
(* n (factorial (- n 1)))))
? ? ? ?
(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) max-counter)))
? ? ? ? ? ? ? ?
1 2 3 4
1 2 3 4 5 6 7 8
以上分别是递归和迭代的阶层，下面是Common Lisp语言版的斐波那契数求法：
(defun fib (n)
(fib-iter 1 0 n))(defun fib-iter (a b count) (if (= count 0) b
(fib-iter (+ a b) a (- count 1))))
? ? ? ? ? ?
1 2 3 4 5 6
借助递归树求解递归式
前面我们已经看到了递归式，也看到了递归树，那么如何借助递归树来求解递归式呢？接下来就来看看吧。
在递归树中，每个结点都表示一个单一问题的代价，子问题对应某次递归函数调用。
通过对树中每层的代价进行求和，就可以得到每层的代价；然后将所有层的代价求和，就可以得要到所有层次的递归调用的总代价。
我们通常用递归树来得出一个较好的猜测结果，然后用代入法来证明猜测是否正确。但是通过递归树来得到结果时，不可避免的要忍受一些”不精确“，得在稍后才能验证猜测是否正确。
因为下面的示例图太难用键盘敲出来了，我就用了手写，希望大家不介意。
如下所示，有一个递归式，我们要借助它的递归树来求解最终的结果。前面所说的忍受“不精确”这里就有2点：
1）我们要关注的更应该是解的上界，因为我们知道舍入对求解递归式没有影响，因此可以将Θ(n2)写成cn2，且为该递归式创建了如下递归树。