递归算法介绍-知识专区-汉码未来

当前位置： Python > 递归算法介绍

admin · 更新于 2021-08-06

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 == 1:
        return 1
    return n * F(n - 1)代码块
1
2
3
4

前两行的语句是递归终止条件，这个是必须要有的，而且必须是递归要能到达的。最后一个 n * F(n - 1) 正是递归调用自身，且每次递归的参数都会减少直到最后的终止条件结束。我们用示例图来演示下 F(5) 执行的递归过程，这样方便我们理解递归调用。

计算F(5)的递归调用

递归算法动态示意图：

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

def F_no_recursive(n):
    s = 1
    for i in range(1, n + 1):
        s = s * i    return s代码块
1
2
3
4
5

可以看到，递归代码相比不使用递归的代码少了 for 循环，并且递归的代码看起来会比较简洁和清楚，这在二叉树的问题中会体现的非常明显。

3. 函数调用过程

在所有的编程语言中，函数的调用都是这样的过程：

将当前调用函数的下一个指令地址压入堆栈，并保存现场环境；
调到调用函数地址去执行；
调用函数执行完成后，调用 ret 指令弹出下一步执行的地址，返回到原来的函数中接着执行下一条语句。

示意图如下：

函数调用过程

自己调用也是一样的过程，并不会说自己调用自己递归就会在函数内部执行，同样是在另一个地址有一份相同的函数代码拷贝，也就是将上图中的函数 B() 换成函数 A()，这幅图同样正确。递归调用的示意图如下：

递归调用示意图

4. 递归算法的缺点

前面说到了递归问题的优点，就是使用递归后整体代码简洁明了，阅读起来让人如沐春风。但是递归方法也会才能在较大问题：

递归太深，容易导致栈溢出异常。前面介绍过，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出；
可能存在大量的冗余计算，算法的时间复杂度呈指数级增长，这个会在后面的递归实例中展示。