递归的内涵与经典应用

摘要：

　　大师 L. Peter Deutsch 说过：To Iterate is Human, to Recurse, Divine.中文译为：人理解迭代，神理解递归。毋庸置疑地，递归确实是一个奇妙的思维方式。对一些简单的递归问题，我们总是惊叹于递归描述问题的能力和编写代码的简洁，但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。本文剖析了递归的思想内涵，分析了递归与循环的联系与区别，给出了递归的应用场景和一些典型应用，并利用递归和非递归的方式解决了包括阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解在内的八个经典问题。

一. 引子

　　 大师 L. Peter Deutsch 说过：To Iterate is Human, to Recurse, Divine.中文译为：人理解迭代，神理解递归。毋庸置疑地，递归确实是一个奇妙的思维方式。对一些简单的递归问题，我们总是惊叹于递归描述问题的能力和编写代码的简洁，但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。在正式介绍递归之前，我们首先引用知乎用户李继刚(https://www.zhihu.com/question/20507130/answer/15551917)对递归和循环的生动解释：

　　 递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。

　　 循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。

　　 上面的比喻形象地阐述了递归与循环的内涵，那么我们来思考以下几个问题：

什么是递归呢？

递归的精髓(思想)是什么？

递归和循环的区别是什么？

什么时候该用递归？

使用递归需要注意哪些问题？

递归思想解决了哪些经典的问题？

这些问题正是笔者准备在本文中详细阐述的问题。

二. 递归的内涵

1、定义 (什么是递归？)

　　 在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。

2、递归思想的内涵(递归的精髓是什么？)

　　 正如上面所描述的场景，递归就是有去（递去）有回（归来），如下图所示。“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁一样；“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。　　

　　 更直接地说，递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。

3、用归纳法来理解递归

　　 数学都不差的我们，第一反应就是递归在数学上的模型是什么，毕竟我们对于问题进行数学建模比起代码建模拿手多了。观察递归，我们会发现，递归的数学模型其实就是 数学归纳法，这个在高中的数列里面是最常用的了，下面回忆一下数学归纳法。

　　 数学归纳法适用于将解决的原问题转化为解决它的子问题，而它的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是归纳结束的那一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷归纳了。总的来说，归纳法主要包含以下三个关键要素：

步进表达式：问题蜕变成子问题的表达式

结束条件：什么时候可以不再使用步进表达式

直接求解表达式：在结束条件下能够直接计算返回值的表达式

事实上，这也正是某些数学中的数列问题在利用编程的方式去解决时可以使用递归的原因，比如著名的斐波那契数列问题。

4、递归的三要素

　　 在我们了解了递归的基本思想及其数学模型之后，我们如何才能写出一个漂亮的递归程序呢？笔者认为主要是把握好如下三个方面：

明确递归终止条件；

给出递归终止时的处理办法；

提取重复的逻辑，缩小问题规模。

1). 明确递归终止条件

　　 我们知道，递归就是有去有回，既然这样，那么必然应该有一个明确的临界点，程序一旦到达了这个临界点，就不用继续往下递去而是开始实实在在的归来。换句话说，该临界点就是一种简单情境，可以防止无限递归。

2). 给出递归终止时的处理办法

　　 我们刚刚说到，在递归的临界点存在一种简单情境，在这种简单情境下，我们应该直接给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的。

3). 提取重复的逻辑，缩小问题规模*

　　 我们在阐述递归思想内涵时谈到，递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，我们需要抽象出一个干净利落的重复的逻辑，以便使用相同的方式解决子问题。

5、递归算法的编程模型

　　 在我们明确递归算法设计三要素后，接下来就需要着手开始编写具体的算法了。在编写算法时，不失一般性，我们给出两种典型的递归算法设计模型，如下所示。

模型一： 在递去的过程中解决问题

function recursion(大规模){

    if (end_condition){      // 明确的递归终止条件

        end;   // 简单情景

    }else{            // 在将问题转换为子问题的每一步，解决该步中剩余部分的问题

        solve;                // 递去

        recursion(小规模);     // 递到最深处后，不断地归来

    }

}

模型二： 在归来的过程中解决问题

function recursion(大规模){

    if (end_condition){      // 明确的递归终止条件

        end;   // 简单情景

    }else{            // 先将问题全部描述展开，再由尽头“返回”依次解决每步中剩余部分的问题

        recursion(小规模);     // 递去

        solve;                // 归来

    }

}

6、递归的应用场景

　　 在我们实际学习工作中，递归算法一般用于解决三类问题：

　　 (1). 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；

　　 (2). 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；

　　 (3). 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

　　在下文我们将给出递归算法的一些经典应用案例，这些案例基本都属于第三种类型问题的范畴。

三. 递归与循环

　　 递归与循环是两种不同的解决问题的典型思路。递归通常很直白地描述了一个问题的求解过程，因此也是最容易被想到解决方式。循环其实和递归具有相同的特性，即做重复任务，但有时使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看，递归和循环并无优劣之别。然而，在实际开发中，因为函数调用的开销，递归常常会带来性能问题，特别是在求解规模不确定的情况下；而循环因为没有函数调用开销，所以效率会比递归高。递归求解方式和循环求解方式往往可以互换，也就是说，如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成循环往往是好的。问题的递归实现转换成非递归实现一般需要两步工作：

　　 (1). 自己建立“堆栈(一些局部变量)”来保存这些内容以便代替系统栈，比如树的三种非递归遍历方式；

　　 (2). 把对递归的调用转变为对循环处理。

　　 特别地，在下文中我们将给出递归算法的一些经典应用案例，对于这些案例的实现，我们一般会给出递归和非递归两种解决方案，以便读者体会。

四. 经典递归问题实战

1. 第一类问题：问题的定义是按递归定义的

(1). 阶乘

1！= 1
对所有n > 1的整数：
n！ = (n * (n-1)！)

【阶乘】

1. （2）斐波纳契数列（Fibonacci Sequence），又称黄金分割数列。
   1、1、2、3、5、8、13、21…

Fib(0) = 1，Fib(1) = 1。
对所有n > 1的整数：
Fib(n) = (Fib(n-1) + Fib(n-2))

（3）汉诺塔问题

已知有三根针分别用A, B, C表示，在A中从上到下依次放n个从小到大的盘子。

现要求把所有的盘子从A针全部移到C针，移动规则是：可以使用B临时存放盘子，每次只能移动一块盘子，而且每根针上不能出现大盘压小盘，找出移动次数最小的方案。

A，B，C三个盘子，分别为初始位，过渡位，目标位：

（1）将最上面的n-1个圆盘从初始位移动到过渡位

（2）将初始位的最底下的一个圆盘移动到目标位

（3）将过渡位的n-1个圆盘移动到目标位

【汉诺塔问题】

【输出结果】

1:A->C
2:A->B
1:C->B
3:A->C
1:B->A
2:B->C
1:A->C
7

4. （4）上台阶有多少种走法：

楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，计算共有多少种不同的走法.

设n阶台阶的走法数为f(n)

n=1 时：有1种走法
n=2 时：有2种走法
n>2时： f(n-1)+f(n-2)

【上台阶问题】

5. （5）递归法求数组最大值：

6. 数组为空：返回0

7. 数组长度为1：返回这个值

8. 数组长度大于1：比较第一个值和剩余元素的最大值（调用）

【数组最大值】

2. 
   

3. （6）杨辉三角

4. 递归求杨辉三角第i行，第j列的值

【杨辉三角求值及输出】

【输出】

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

3. （7）回文串

长度为1：返回True
长度大于1：
判断：最外层两个是否相同
不同：返回False
相同：内移一层（调用）

【判断是否为回文串】

（8）字符串的全排列

原文链接：https://blog.csdn.net/qq_42015869/article/details/79996227

全排列：

1、列表只有一个元素[a]，它的全排列只有a。

2、列表有两个元素[a, b]，它的全排列为[a, b], [b, a]：

{ 将第一个元素a固定，对b进行全排列得到[a, b]。

将第一个元素与第二个元素交换得到[b, a]。

将b固定，对a进行全排列，得到[b, a] }

3、列表有三个元素[a, b, c]

{ 将a固定，对bc进行全排列{ 将b固定，对c全排列[abc]。交换bc，将c固定对b进行全排列[acb] }

交换ab，[b, a, c] 对ac进行全排列{ … }

… …}

4、列表有n个元素，将第一个元素固定，对剩下n - 1个元素进行全排列。

将第一个元素依此与其他元素交换，对每次交换后剩下的n-1个元素进行全排列。

5、对剩下的n - 1个元素全排列，同上，固定后对n - 2排列。

6、直到数组数量为1，全排列就是它自己，完成一次排列。

【字符全排列】

---------------------------------------------------

版权声明：本文选摘自CSDN博主「书呆子Rico」和「是DRR啊」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接1：https://blog.csdn.net/justloveyou_/article/details/71787149

原文链接2：https://blog.csdn.net/qq_25041667/article/details/100553037