递归算法介绍

发布时间：2023-06-28 14:23:40 所属栏目：教程来源：

导读：本节将主要介绍基础算法中最为常见和最为简单的算法：递归算法。

1. 递归算法原理详解
递归算法，通常是把一个大型复杂的问题，一次次通过递归调用而层层转化为一个与原问题相似的规模较小的问题来求解，基本思想

本节将主要介绍基础算法中最为常见和最为简单的算法：递归算法。

1. 递归算法原理详解
递归算法，通常是把一个大型复杂的问题，一次次通过递归调用而层层转化为一个与原问题相似的规模较小的问题来求解，基本思想是将大问题一步步化为小问题，递归算法只需少量的程序就可表达对大问题的计算过程所需要的多次重复计算，大大地减少了程序代码。从代码的角度上来看就是函数调用自身，我们称之为递归。

2. 举例说明递归算法
我们现在用一个简单的例子进行说明：假设我们需要写一个函数去求数字n的阶乘。当输入5时，输出5!=120，当输入6时，输出6!=720。如果我们编写了一个函数 F(n) 用来求解输入参数 n 的阶乘值，很明显我们可以发现这样一个递归关系：F(n) = n * F(n - 1)，那么我们求解 F(n) 的代码可以这样写：

递归求 5 的阶乘 Python 实现
def F(n):
if n == :
return
return n * F(n - )
前两行的语句是递归终止条件，这个是必须要有的，而且必须是递归要能到达的。最后一个 n * F(n - 1) 正是递归调用自身，且每次递归的参数都会减少直到最后的终止条件结束。

递归的思想就是在不停调用本身往下执行，直到终止条件达到然后再回推结果。递归带来的好处非常明显，就是减少代码，让代码看起来简洁明了。假如我们要使用非递归算法来求解 n 的阶乘，代码如下：

def F_no_recursive(n):
s =
for i in range(, n + ):
s = s * i
return s
可以看到，递归代码相比不使用递归的代码少了 for 循环，并且递归的代码看起来会比较简洁和清楚，这在二叉树的问题中会体现的非常明显。

3. 函数调用过程
在所有的编程语言中，函数的调用都是这样的过程：
将当前调用函数的下一个指令地址压入堆栈，并保存现场环境；
调到调用函数地址去执行；
调用函数执行完成后，调用 ret 指令弹出下一步执行的地址，返回到原来的函数中接着执行下一条语句。

4. 递归算法的缺点
前面说到了递归问题的优点，就是使用递归后整体代码简洁明了，阅读起来让人如沐春风。但是递归方法也会才能在较大问题：
递归太深，容易导致栈溢出异常。前面介绍过，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出；
可能存在大量的冗余计算，算法的时间复杂度呈指数级增长，这个会在后面的递归实例中展示。

5. 解决递归问题的通用思路
对于一个递归问题，我们会有一套模板去实现这样一个递归算法：
递归终止条件：一定和必须要有；
递归公式：递归的核心，找不出递归公式的，也就无法使用递归算法来解决。这里实现递归算法的递部分；
返回预定结果：返回我们预先定好的结果参与递归算法的归部分。

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!