第一章 数据结构与算法基本概念
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 时结束递的过程，开始归，归的时候从递的下面一行开始运行。
程序运行结果：
