【算法】递归、搜索与回溯——简介

简介：递归、搜索与回溯，本节博客主要是简单记录一下关于“递归、搜索与回溯”的相关简单概念，为后续算法做铺垫。

递归、搜索、回溯的关系：

1.递归

1.1递归概念

函数自己调用自己

2.2递归意义

递归具有多种意义，比如二叉树的遍历、快排、归并…

本质：用于解决主问题的方法f，在子问题中也可以适用，即有限“套娃”

2.3学习递归

• 递归展开图
• 多练习题目
• 宏观看待递归过程

• 不要在意递归细节展开
• 将递归函数看成一个黑盒
• 认为黑盒可以解决此问题

2.4写递归代码步骤

递归代码往往比较简短，但是要注意思考的步骤：

• 1.函数头的设计：找相同的子问题，根据需要设计参数
• 2.函数体的编写：只关心一个子问题的解决方案
• 3.函数结束：注意递归结束条件

2.搜索

搜索 分为深度 优先搜索(dfs) 和 广度搜索(bfs) ，仍属于暴力遍历。

以二叉树为例，来解释dfs与bfs：

dfs：

bfs：

拓展：全排列问题也可以用深度优先遍历来进行解决。

例如：

3.回溯与剪枝

回溯：尝试某种情况发现走不通所进行的回到最近分界点的过程。

剪纸：当通过会u是回到分界点时，已经确定某一条鲁不具有可行性，从而排除这种选择称之为剪枝。

EOF