Chapter1——递归和迭代

一.递归

1.1 定义

    对于递归的规范性定义可以参考*：递归，但是我觉得这个定义对于初学者来说比较晦涩，下面是我在知乎上搜到的一个形象的比喻：

我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。
来源：知乎

以上部分正好形象的说明了递归算法要具备的三个条件：

1.递归前进段和递归返回段。
2.边界条件。
3.当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

话不多说，下面开始例题分析。

1.2 例题分析

(1).阶乘问题

对于阶乘问题，显然可以给出如下定义：

n!={1n∗(n−1)!if n = 0if n ≥ 1  $$n!=\{\begin{array}{ll}1& \text{if n = 0}\\ n\ast (n-1)!& \text{if n }\ge \text{ 1 }\end{array}$$

这样的话，就将一个 n 阶问题转化成了一个 n-1 阶的问题。而问题的边界条件即为 n == 0时，当问题分解至 n == 0，则可将子问题的结果一层一层返回，直至得出最后的结果返回主函数。示例代码如下：

#include <iostream>
using namespace std;
int Fac(int n);
int main() {
int n;
cout << "Please Input n: " << endl;
cin >> n;
cout << n << "! = " << Fac(n) << endl;
return 0;
}

int Fac(int n) {
if (n == 0) {
return 1;
    } else {
return n * Fac(n - 1);
    }
}

可以模拟递归分解原问题的过程以及将结果返回原问题的过程，加深对递归的理解，如下:

#include <iostream>
using namespace std;
int Fac(int n, int step);
int main() {
int n;
cout << "Please Input n: " << endl;
cin >> n;
cout << n << "!求解过程如下: " << endl;
cout << Fac(n, 0) << endl;
return 0;
}

int Fac(int n,int step) {
if (n == 0) {
return 1;
    } else {
int temp = step, tempValue;
while (temp--) {
cout << " ";
        }
cout << n << "*" << n - 1 << "!" << endl;
        tempValue = Fac(n - 1, step + 1);
while (step--) {
cout << " ";
        }
cout << n << "*" << tempValue << endl;
return n * tempValue;
    }
}

程序运行结果:

Please Input n: 
8
8!求解过程如下: 
8*7!
7*6!
6*5!
5*4!
4*3!
3*2!
2*1!
1*0!
1*1
2*1
3*2
4*6
5*24
6*120
7*720
8*5040
40320

(2).斐波那契数列

    问题描述：斐波那契数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：
F1=1,F2=1,Fn=Fn−1+Fn−2（n>=3，n∈N+） $F_1=1,F_2=1,F_n=F_{n-1}+F_{n-2}（n>=3，n\in N^{+}）$
有了以上的的递归关系，不难得出以下的代码：

#include <iostream>
using namespace std;
int Fib(int n);
int main() {
int n;
cout << "Please Input n: " << endl;
cin >> n;
cout << "The " << n << "th Fib is: " << Fib(n) << endl;
return 0;
}

int Fib(int n) {
if (n == 1 || n == 2) {
return 1;
    } else {
return Fib(n - 1) + Fib(n - 2);
    }
}

     斐波那契数列在数学和生活以及自然界中都非常有用。曾经自己在考研的时候常数项级数求和也有涉及斐波那契数列通项的问题，所以说这也是一个很有趣的数列，关于斐波那契数列的更多知识可以参考：
斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？

(2).汉诺塔问题

    说到递归问题，必然是要提到汉诺塔问题的，汉诺塔问题描述如下：
    有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
分析：
    根据问题提示，很容易想到，我在移动n个圆盘的时候，由于大盘不能叠在小盘上面，所以我肯定想怎么样能先把最后一个盘子移到C杆去，这样的话就不用再管最大的那个盘子了。那么顺着这样的思路，我要把最后一个盘子移到C杆去，那这最后一个大盘子上的n-1个盘子要先移开才行。这n-1个盘子移开之后，然后我就可以把最后一个盘子（也就是最大的那个）移到C杆去。所以我可以先用B杆，帮我先暂存这上面的n-1个盘子。但是每次只能移动一个圆盘，所以我要借助剩下的杆子，也就是C杆，来协助把这n-1个盘子移到B杆上，然后才能把最大的盘子移到C杆上面去。当把最大的盘子移到C杆之后，剩下的问题就简单了，我只需要将剩下的n-1个盘子移到C杆就完成目标了(同样要借助剩下的杆子)。问题分析完毕，那么用简略的语言总结一下:

首先，以A杆作为起始杆，借助C杆作为中间杆(起协助作用)，将n-1个盘子移至B杆；
其次，将底下”最大的盘子”从A杆(起始杆)移至C杆(目标杆)；
最后，以B杆作为起始杆，借助A杆作为中间杆(起协助作用)，将n-1个盘子移至C杆；

而核心问题来了，每次只能移动一个圆盘，所以第一步移动n-1个盘子移至B杆的操作显然是不能一蹴而就的，除非当n-1等于1的时候，就可以直接移动了，因此第一步移动n-1个盘子移至B杆的操作还要继续分解，直至分解成可以直接操作的子问题。而该问题的分解过程与上述过程完全一致，因此依旧是递归这个过程分解原问题。同样的，最后一步的过程以此类推。这样，原问题就被分解成两个n-1阶的子问题和一个1阶的子问题。下面用简单的数学语言概括一下(设n阶汉诺塔问题为 f(n) $f(n)$)，即为：

f(n)={1f(n−1)+1+f(n−1)if n = 1if n ≥ 1  $$f(n)=\{\begin{array}{ll}1& \text{if n = 1}\\ f(n-1)+1+f(n-1)& \text{if n }\ge \text{ 1 }\end{array}$$

因此，问题就抽象成了递归问题，也就得到了以下完整代码：

#include <iostream>
using namespace std;
void Hanoi(char startPos, char tranPos, char targPos, int n);
void move(char startPos, char targPos);

int main() {
int n;
cout << "Please Input n: " << endl;
cin >> n;
    Hanoi('A', 'B', 'C', n);
return 0;
}

void Hanoi(char startPos, char tranPos, char targPos, int n) {
if (n == 1) {
        move(startPos, targPos);
    } else {
        Hanoi(startPos, targPos, tranPos, n - 1);
        move(startPos, targPos);
        Hanoi(tranPos, startPos, targPos, n - 1);
    }
}

void move(char startPos, char targPos) {
cout << startPos << " -> " << targPos << endl;
}

运行情况：

Please Input n: 
1
A -> C

Please Input n: 
2
A -> B
A -> C
B -> C

Please Input n: 
3
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

下面简单证明为什么这样的做法是步数最小的做法:

数学归纳法证明过程如下:

当n == 1，结果显然为1。

假设 f(n−1) $f(n-1)$确实是把n-1个盘子集体挪动的最小步数，我们要证明 f(n) $f(n)$是把n个盘子集体挪动的最小步数。

1.在把n个盘子从A移动到C的过程中，必然存在一步，是把最大的盘子从A拿出来。要想把最大的盘子从A移动到别的某个柱子上（B或C），就必须保证剩下的n-1个盘子先移走，得好好堆在剩下那个柱子（C或B）上。要保证n-1个盘子都在剩下那个柱子上，至少得付出 f(n−1) $f(n-1)$次移动。

2.在把n个盘子从A移动到C的过程中，必然存在一步，是最大的盘子被放到了C上，而且此后再也没动过。在这步实行之前，最大的盘子要么在A要么在B上，而相应地别的n-1个盘子要么在B要么在A上。在这步实施之后，我们只要花至少 f(n−1) $f(n-1)$的步数把n-1个盘子从要么B要么A挪动到C上就行了。这些步数必然和步骤1中的步数不重叠，因为这时候最大盘子在C上，而步骤1中最大盘子在A上。

3.最大的盘子至少被挪动了一次。而且这一次肯定没被算在步骤1或步骤2的”至少 f(n−1) $f(n-1)$步”中，因为后者只挪动较小的那n-1个盘子。

综上所述: f(n) $f(n)$的最小值即为: f(n)=f(n−1)+1+f(n−1)=2∗f(n−1)+1 $f(n)=f(n-1)+1+f(n-1)=2\ast f(n-1)+1$
得证

有了递推公式，那么是否可以得到通项公式呢？我们观察这个式子的前几项：
f(1)=1 $f(1)=1$

f(2)=2∗f(1)+1=3 $f(2)=2\ast f(1)+1=3$

f(3)=2∗f(2)+1=2∗(2∗f(1)+1)+1=22∗f(1)+21∗1+1(20)=23−1=7 $\begin{array}{rl}f(3)& =2\ast f(2)+1\\ & =2\ast (2\ast f(1)+1)+1\\ & =2^2\ast f(1)+2^1\ast 1+1(2^0)\\ & =2^3-1\\ & =7\end{array}$

f(4)=2∗f(3)+1=2∗(2∗f(2)+1)+1=22∗f(2)+21∗1+1(20)=22∗(2∗f(1)+1)+21∗1+20=24−1=15 $\begin{array}{rl}f(4)& =2\ast f(3)+1\\ & =2\ast (2\ast f(2)+1)+1\\ & =2^2\ast f(2)+2^1\ast 1+1(2^0)\\ & =2^2\ast (2\ast f(1)+1)+2^1\ast 1+2^0\\ & =2^4-1\\ & =15\end{array}$

... $...$
很显然，这是一个等比数列的求和问题，则：
f(n)=20+21+22+...+2n−2+2n−1=2n−1 $f(n)=2^0+2^1+2^2+...+2^{n-2}+2^{n-1}=2^n-1$

即得通项公式为:

f(n)=2n−1 $$f(n)=2^n-1$$

实际上，所有原问题分解成子问题的过程，用图表示的话，是一棵三叉树，最后无法再分解的子问题即为该三叉树的叶节点，而整个原问题的规模即为所有子问题的和，即该三叉树叶节点节点总数。
图示演示(三阶 & 四阶汉诺塔问题):


关于汉诺塔问题的更多知识可以参考：
经典汉诺塔问题分析
如何理解汉诺塔的递归？

1.3 递归问题总结：

关于递归问题，自己有以下的几点看法：
1.递归问题的精髓在于能否把原问题分解成相似或相近的子问题，如上述的两个问题；
2.设计递归模型时，要善于运用数学模型，用数学符号将问题抽象成一般问题，再寻找递归体与终止条件；
3.递归只是求解问题的一种方法，并不是说以上问题只能用递归求解，实际上很多问题用递归求解只是代码简洁易理解，而并不是最优解法。初学时，若对比较复杂的递归问题不是很理解，可以暂放。等过段时间再来看，循序渐进式学习。

---

二.迭代

2.1 定义

对于迭代的规范性定义可以参考*：迭代

迭代是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。

迭代的定义理解起来是没有难度的，下面以一道经典例题来说明。

2.2 例题分析

    同样是递归问题中的例题1 & 例题2，仔细分析一下，是否可以用另外的方法求解？

(1).阶乘问题

由于阶乘问题给出如下定义：

n!={1n∗(n−1)!if n = 0if n ≥ 1  $$n!=\{\begin{array}{ll}1& \text{if n = 0}\\ n\ast (n-1)!& \text{if n }\ge \text{ 1 }\end{array}$$

而我们只需要求得 n! $n!$ 的值即可，因此我们是否可以这么思考？即：

0! = 1
1! = 1 * 0!
2! = 2 * 1!
…
n! = n * (n-1)!

从以上推导过程可以知道，我们可以把上一项的计算结果作为下一项的乘数，这也就是迭代的精髓所在。完整实现代码如下：

#include <iostream>
using namespace std;
int Fac2(int n);
int main() {
int n;
cout << "Please Input n: " << endl;
cin >> n;
cout << n << "! = " << Fac2(n) << endl;
return 0;
}

int Fac2(int n) {
int initValue = 1,tempValue;
for (int i = 1; i <= n;i++) {
        tempValue = i * initValue;
        initValue = tempValue;
    }
return initValue;
}

(2).斐波那契数列问题

按照斐波那契数列的定义：
F1=1,F2=1,Fn=Fn−1+Fn−2（n>=3，n∈N+） $F_1=1,F_2=1,F_n=F_{n-1}+F_{n-2}（n>=3，n\in N^{+}）$
同样我们可以试着推导：

  F1=1,F2=1F3=F2+F1=2F4=F3+F2=3F5=F4+F3=5…Fn=Fn−1+Fn−2 $$\begin{gathered} F_1=1,F_2=1 \\ {F}_3=F_2+F_1=2 \\ {F}_4=F_3+F_2=3 \\ {F}_5=F_4+F_3=5 \\ \dots \\ {F}_n=F_{n-1}+F_{n-2} \end{gathered}$$

从以上推导过程可以知道，当计算 Fn $F_n$时，我们可以利用上两项的计算结果 Fn−1 $F_{n-1}$和 Fn−2 $F_{n-2}$，完整实现代码如下：

#include <iostream>
using namespace std;
int Fib(int n);
int main() {
int n;
cout << "Please Input n: " << endl;
cin >> n;
cout << "The " << n << "th Fib is: " << Fib(n) << endl;
return 0;
}

int Fib(int n) {
int tempValue1 = 1, tempValue2 = 1, sum = 1;
for (int i = 3; i <= n; i++) {
        sum = tempValue1 + tempValue2;
        tempValue1 = tempValue2;
        tempValue2 = sum;
    }
return sum;
}

---

三.递归和迭代的对比

以上述斐波那契数列数列的例子，说明递归与迭代的对比：

#include <iostream>
#include <ctime>
using namespace std;
int iterFib(int n);
int recurFib(int n);

int main() {
int n;
    clock_t startSeconds, endSeconds;
cout << "Please Input n: " << endl;
while(cin >> n) {
        startSeconds = clock();
cout << "The " << n << "th Fib is: " << iterFib(n) << endl; 
        endSeconds = clock();
cout << "迭代方法的计算时间为: " << endSeconds - startSeconds << "ms" << endl;

        startSeconds = clock();
cout << "The " << n << "th Fib is: " << recurFib(n) << endl;    
        endSeconds = clock();
cout << "递归方法的计算时间为: " << endSeconds - startSeconds << "ms" << endl;

cout << "Please Input n: " << endl;
    }
return 0;
}

int recurFib(int n) {
if (n == 1 || n == 2) {
return 1;
    } else {
return recurFib(n - 1) + recurFib(n - 2);
    }
}

int iterFib(int n) {
int tempValue1 = 1, tempValue2 = 1, sum = 1;
for (int i = 3; i <= n; i++) {
        sum = tempValue1 + tempValue2;
        tempValue1 = tempValue2;
        tempValue2 = sum;
    }
return sum;
}

测试过程(由于尾递归可能会被优化成迭代，因此命令行运行去掉优化)：

从上图以及以上递归和迭代的例子可以说明，递归中存在大量重复计算，并且问题规模是指数级的，一般情况下能用迭代解决问题则优先使用迭代的方法。更多分析可以参考：
递归和迭代算法深入分析(入门篇)
深究递归和迭代的区别、联系、优缺点及实例对比