递归和迭代 - 图文

迭代是一个重复过程，它的目的是接近既定的目标或结果。每次重复的过程也称为”迭代“，作为迭代的结果都将作为下一次迭代的起点。

迭代在计算中是指的计算机程序中的重复的语句块。它可以表示两个专业术语，同义重复，以及描述一种具有可变状态重复的具体形式。然后令人费解的是，它也可以表示通过显式重复结构的任何重复，而不管其可变性。

在第一个意义上，递归是迭代的一个例子，但通常用”递归“来标记，而不作为”迭代“的例子。

在第二个意义上，（更加狭义地）迭代描述了一种编程风格。这与一个有着更有声明性方法的递归有着鲜明的对比。

第三个意义上，使用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，且为该递归式创建了如下递归树。