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