【递归算法】递归算法的快速入门

🐋作者简介：博主是一位.Net开发者，同时还是RPA和低代码平台的践行者。
🐬个人主页：会敲键盘的肘子
🐰系列专栏：数据结构与算法
🦀专栏简介：图解经典算法，C#代码实现，算法升级版。
🐶座右铭：总有一天你所坚持的会反过来拥抱你。

🌈写在前面：

本文主要介绍了递归的基本概念、应用场景和原则。

活动地址：CSDN21天学习挑战赛

👉本文关键字：递归算法、迷宫问题、八皇后问题、C#

1️⃣ 基本概念

♈ 概念

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

上述定义来自百度百科

递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

♉ 条件

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

♊ 斐波纳契数列

斐波纳契数列是典型的递归案例：

递归关系就是实体自己和自己建立关系。
$$Fib(0)=1，Fib(1)=1，Fib(n)=(Fib(n-1)+Fib(n-2))$$
尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：
$$1！=1$$
对所有n > 1的整数：
$$n!=n\ast (n-1)!$$
这种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。

2️⃣ 应用场景

♈ 解决的问题

1. 各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题；
2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等；
3. 数据的结构形式是按递归定义的，如二叉树、广义表等，由于结构本身固有的递归特性；

♉ 案例

1. 迷宫问题
   如何求出最短路径?
   

   说明
   小球得到的路径，和程序员设置的找路策略有关，即找路的上下左右的顺序相关，再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化。
   思路

   • 定义二维数组map[][]为迷宫；
   • 当map[i][j]为0时表示没有走过，当1时表示为墙，当2时表示通路可以走，当3时表示此路不通；
   • setWay()方法表示找路。返回一个bool类型的值，当为true时表示该路可以走通，当为false时表示该路走不通；
   • 在走出迷宫(到达终点)时，需要我们自己定制一个方法(道路)，比如我们按照下->右->上->左。一步一步向前探索，如果该点走不通，再回溯。
   • 每当我们走到一个点的时候，把该点的值设置为2，就是暂时假定该路能走通，至于到底走通没走通，得看后面有没有找到通路。
   • 如果后面的路能走通，从最后一个点开始返回，setWay()递归调用都返回true，如果后面的路不能走通，那么将当前的点设置为3，表示是思路，即走不通，回溯到上一个点，看看其他方向能不能走通。

2. 八皇后问题介绍
   八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路

• 第一个皇后先放第一行第一列；
• 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适；
• 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解；
• 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第 - 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤 。

⭐写在结尾：

文章中出现的任何错误请大家批评指出，一定及时修改。

希望看在这里的小伙伴能给个三连支持！