算法学习：递归算法的理解与举例

快来打我* 2022-10-31 00:40 151阅读 0赞

原文：[https://blog.csdn.net/sinat\_38052999/article/details/73303111][https_blog.csdn.net_sinat_38052999_article_details_73303111]

# 1. 摘要 #

1.  递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门；
2.  循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。

上面的比喻形象地阐述了递归与循环的内涵

# 2. 递归的内涵 #

1.  定义：  
    在数学和计算机科学中，递归是指在函数的定义中，使用函数自身的方法。实际上，递归顾名思义，其中包含了两个意思：递 和 归，这就是递归思想的精华所在。
2.  递归思想精髓：  
    正如上面所描述的场景，递归就是有去（递去）有回（归来），如下图所示。

“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁一样；

“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTk4NzQ5_size_16_color_FFFFFF_t_70]　 更直接地说，递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况

1.  递归三要素：

（1）明确递归终止条件；

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

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

我们刚刚说到，在递归的临界点存在一种简单情境，在这种简单情境下，我们应该直接给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的  
　　  
（3）提取重复的逻辑，缩小问题规模。

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

（4）边界条件和递推通式是递归定义的两个基本要素，缺一不可

①边界条件：至少有一条初始定义是非递归的，如汉诺塔的H(0)=0，阶乘的0!=1。  
②递归通式：由已知函数值逐步计算出未知函数值，如汉诺塔的H(0)=0，可以推算出H(1)=H(0)+1+H(0)。

1.  递归算法的编程模型

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

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

# 3. 递归的几个经典应用场景 #

[https_blog.csdn.net_sinat_38052999_article_details_73303111]: https://blog.csdn.net/sinat_38052999/article/details/73303111
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTk4NzQ5_size_16_color_FFFFFF_t_70]: /images/20221024/e3c888297e284e49af9566ad095f0f15.png