第一章 数据结构与算法基本概念
1.1 数据结构定义
数据结构：相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构、散列结构、树形结构和图形结构等。
1.2 算法定义
算法：求解具体问题的步骤描述，代码上表现出来是解决特定问题的一组有限的指令序列。
1.3 递归与迭代
本节参考了《Hello 算法》第二章内容。
1.3.1 迭代
迭代（iteration）是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。
下面以 for 循环为例，求 1+2+3+…+100 的和。
int forLoop(int n) {
int ret = 0;
// 循环求和
for (int i = 1; i <= n; ++i) {
ret += i;
}
return ret;
}
1.3.2 递归
递归（recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。
- 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到'终止条件'。
- 归：触发'终止条件'后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。
而从实现的角度看，递归代码主要包含三个要素。
- 终止条件：用于决定什么时候由'递'转'归'。
- 递归调用：对应'递'，函数调用自身，通常输入更小或更简化的参数。
- 返回结果：对应'归'，将当前递归层级的结果返回至上一层。
比如下面代码：
int recurSum(int n) {
// 1 终止条件
if (n == 1) {
return 1;
}
// 2 递归调用
int ret = recurSum(n - 1) + n;
cout << "ret = " << ret << endl;
// 3 归：返回结果
return ret;
}
理解和总结：每次递归都开辟一个栈帧开始递的过程，然后当 n=1 时结束递的过程，开始归，归的时候从递的下面一行开始运行。
程序运行结果：
/* ret =3 ret =6 ret =10 ret =15 */
1 递归和迭代的思想比较
以 1+2+3+…+100 为例，虽然递归和迭代都能求出这个问题，但是这两种完全不同的思考和解决问题的范式。
迭代：'自下而上'地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。比如先求 1+2=3，然后再求 3+4，…，这样的方法最后求出 sum() + 100。从小数一直累加的方法。
递归：'自上而下'地解决问题。先将远问题分解为更小的问题，这些子问题和原问题有相同的形式。然后再将子问题分解为更小的子问题，直到基本情况时停止。比如上面的求和代码中，递的过程就是分解子问题 f(n) = n+f(n−1)，将 100 分解为 99+100, 98+99 的过程，一直分解为 1+2，然后开始归。
2 调用栈
递归函数每次调用自身时，系统都会为新开启的函数分配一个栈空间。而迭代只有一个栈空间，因此递归比迭代更加消费内存空间。
函数调用会产生额外的开销，因此递归比循环效率更低。
3 尾递归
如果函数在返回前的最后一步才进行递归调用，则函数可以被编译器优化，使其在空间上与迭代相当，这中情况称为尾递归。
普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。求和操作是在'归'的过程中执行的，每层返回后都要再执行一次求和操作。
尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。
int tailRecSum(int n, int ret) {
// 1 终止条件
if (n == 0) {
return ret;
}
// 2 递归调用
return tailRecSum(n - 1, ret + n);
}
求和操作是在'递'的过程中执行的，'归'的过程只需层层返回。
4 递归树
当处理与'分治'相关的算法问题时，递归往往比迭代的思路更加直观、代码更加易读。以'斐波那契数列'为例。
问题 给定一个斐波那契数列 0, 1, 1, 2, 3, 5, 8, 13, …，求该数列的第 n 个数字。 数列的前两个数字为 f(1) = 0 和 f(2) = 1。 数列中的每个数字是前两个数字的和，即 f(n) = f(n − 1) + f(n − 2)。
代码实现：
int fib(int n) {
// 终止条件
if (n == 1 || n == 2) {
return n - 1;
}
// 递归调用 f(n) = f(n-1) + f(n-2)
int ret = fib(n - 1) + fib(n - 2);
return ret;
}
上面代码，在函数内递归调用了两个函数，这意味着从一个调用产生了两个调用分支，这样的递归会产生一个递归树，层数为 n 的递归树，以 5 层为例子。
递归体现了'将问题分解为更小子问题'的思维范式，这种分支策略至关重要。
5 递归和迭代对比
为了理解递归过程，使用栈来模拟递归的过程：
int forLoopRecurSum(int n) {
// 1 终止条件
stack<int> s;
int ret = 0;
// 模拟递的过程
for (int i = n; i > 0; --i) {
s.push(i);
}
// 归的过程
while (!s.empty()) {
ret += s.top();
s.pop();
}
return ret;
}