第二章 递归和回溯

递归

递归的含义：任何调用自身的函数称为递归。用递归求解问题要点在于递归函数调用自身取解决一个规模比原始问题小一些的问题，这个过程称为递归步骤。递归步骤会导致更多的递归调用，因此保证递归过程能够正确终止是很重要的。每次函数都会用比原问题规模更小的问题来调用自身，问题会随着规模不断变小必然能收敛到基本情形。

递归的意义：递归代码通常是比迭代代码更加简洁易懂的。一般来说，在编译或解释时，循环会转化为递归函数。当任务能被相似的子任务定义时，使用递归处理十分有效。例如排序，搜索，遍历等问题往往有简洁的递归解决方案。

递归的格式：递归函数在执行一个任务时，需要调用函数自身来完成一些子任务。而有时，函数不需要继续调用函数自身就可以完成当前子任务，此时这种情况我们称为基本情形，而需要调用自身来完成子任务的情况称为递归情形，如下所示

image.png

递归和迭代的比较：

对于递归来说，其特点如下：

• 到达基本情形时，递归终止
• 递归调用需要额外的空间用于栈帧(内存)开销
• 如果出现无穷递归，程序可能会耗尽内存，并出现栈溢出
• 有些问题用递归的方式更易解答

迭代的特点如下：

• 循环条件为false时，迭代终止
• 每次迭代不需要额外的内存开销
• 由于没有额外的内存开销，所以当出现死循环时，程序会一直循环执行
• 采用迭代求解问题可能不如递归解决方案那样显而易见

总结：

• 递归算法有两类情形：基本情形和递归情形
• 每个递归函数必须终止于基本情形
• 通常，迭代解决方案比递归解决方案更加有效（因为后者需要额外的函数调用开销）
• 迭代算法通常是可以用递归算法来替换的，而有些递归算法并不能用迭代求解

递归算法的经典用例：

• 斐波那契数列，阶乘
• 归并排序，快速排序
• 二分查找
• 树的遍历（前中后序遍历）及很多树相关问题
• 图的遍历（深度优先，广度优先搜索）
• 动态规划
• 分治算法
• 汉诺塔问题
• 回溯算法

递归的问题示例：

image.png

进阶的问题参见具体数学第一章内容

image.png

回溯

回溯的定义：回溯是一种采用分治策略进行穷举搜索的方法

• 有时求解一个问题最好的算法是尝试所有可能性
• 这种方式通常很慢，但通过一些工具能辅助该过程
• 工具：生成基本对象的算法，如二进制串(位二进制串有种可能性)，排列()，组合()，一般字符串(长度为的进制串有种可能性)等
• 通过剪枝回溯可以加速穷举搜索

回溯算法的经典用例：

• 二进制串：产生所有的二进制串
• 生成进制串
• 背包问题
• 广义字符串
• 哈密顿回路
• 图着色问题

回溯的问题示例：

image.png
image.png

本章只是起到一个引导作用，更多详细内容在后续章节会详细介绍