Python学习笔记（11）——递归函数

发表于   |   分类于   |  

本章继续学习函数的知识。

本文仅供个人记录和复习，不用于其他用途

什么是递归函数

函数内部可以调用函数，如果调用的是自己，那么就是递归函数。平常我们使用的递归函数，都是为了计算某些具有规律的问题，比如计算n!。

当然，递归必须要有退出条件，比如计算阶乘时，计算到一定数字就要退出，否则会陷入死循环导致程序崩溃。如果对递归的知识很感兴趣的话，可以去看我的数据结构与算法。

递归实现

既然知道了原理，那么实现起来就很简单了，比如我们拿n!为例：

1
2
3
4
def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

之前我也讲过，所有循环都可以用递归实现，而不是所有递归都可以用循环实现。不过，递归看起来简洁但是逻辑不太清晰，而循环要更加清晰但是代码较长。

另外，递归存在的最大问题，就是对资源的占用。试想一下，每一个函数都需要占据一定的内存，而递归所做的事情则是在一个函数结束前，再掉用一个函数。如果调用次数不多，那么没什么问题。如果是类似于fact(1000)，那么可能会发生栈溢出（函数调用通过栈实现）。

尾递归

为了防止栈溢出，我们可以使用所谓的尾递归，你也可以把它看做是一种特殊的循环：

1
2
3
4
5
6
7
def fact(n):
    return factIter(n, 1)
def factIter(num, product):
    if num == 1:
        return product
    return factIter(num - 1, num * product)

那么这个看起来有什么不同吗？我们可以看到，函数返回值不再有运算，至于num - 1和num * product会在函数调用前计算。

我们所谓的尾递归是指函数返回时，只掉用自己本身，而不会进行运算。如果要进行运算，那么势必就要等待函数返回结果，那样就会导致栈溢出。如果函数只返回本身，那么如果进行了尾递归优化，就不会发生栈溢出。

然而，基本没有语言对尾递归做了优化，所以哪怕你在python中这么写，也只会产生和普通递归一样的结果。

我们可以看一看二者的差别，首先是普通递归：

fact(5)
5 * fact(4)
5 * (4 * fact(3))
5 * (4 * (3 * fact(2)))
5 * (4 * (3 * (2 * fact(1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24

然后是尾递归：

fact_iter(5, 1)
fact_iter(4, 5)
fact_iter(3, 20)
fact_iter(2, 60)
fact_iter(1, 120)