# python3小白课：递归函数

### 递归函数的定义

在一个函数的定义中，可以调用其他函数来完成一些操作。但如果在函数的定义内部调用函数自身（即自己调用自己），那么这个函数就称之为递归函数，递归函数是一种有趣的函数定义形式，在某些业务场景之下十分便利。比如文件层级遍历、目录树、一些数学算法等。

本节课我们就拿一个简单的数学算法来讲讲递归函数是如何定义的以及注意点。

> 引用百科的内容：
>
> 斐波那契数列（Fibonacci sequence），又称黄金分割数列、兔子数列，是数学家列昂纳多·斐波那契于1202年提出的数列。
>
> 斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始，每一项都等于前两项之和，递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。
>
> 在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

要完成斐波那契数列的递推生成，使用递归函数就是一个不错的选择。我们先来看一下代码：

```python
# coding:utf-8
def fib(n):
    if n in [1, 2]:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
fib_seq = [fib(i) for i in range(1, 31)]
print(fib_seq)
```

如代码所示，我们通过for表达式循环获取了一个斐波那契数列列表，共30个元素，传入是要求这个n要大于等于1，这里就不写其他的判断语句了，为了说明的简洁。

可以看到进入函数之后，首先判断n是否为1或者2，如果是的话，则是固定的数1，如果大于等于3的话，就会返回调用自身函数的表达式，只不过传入的参数变成了`n -1`或者`n - 2`。这样传入之后，就会各自调用自身来进行计算，当减少到一定程度之后，一定会到获取`fib(1)、fib(2)`的值，而这两个值是固定的，为1。所以整个函数调用得以结束。

> [!danger]
>
> 编写递归函数时，当自身自调用到一定程度的时候，它能够获取确定的值，不再调用自身，如果不能，就会形成一种死循环，这是无意义的。
>
> 因此在写递归函数的时候，需要注意，递归一定要朝着已知的方向进行。

---

### 防止堆栈溢出

> [!note]
>
> 这部分是比较偏底层原理的内容，如果不好理解，可以跳过。

使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

> [!danger]
>
> 因此我们在使用递归函数的时候，需要注意调用递归的层级不要太深，太深容易导致栈溢出，会报错，在python中目前没有良好的机制来处理，所以是存在这个问题的。

多深呢？比如上千层的递归调用。

还有一种情况是递归程度深，系统运算困难，速度慢。就拿刚才讲到的斐波那契数列来说，我们把代码改成这样：

这次我们一次次获取数列中的每个值，打算跑1000次。

```python
# coding:utf-8
def fib(n):
    if n in [1, 2]:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
for i in range(1, 1001):
    print("i: %s, fib(i): %s" % (i, fib(i)))
```

我们来运行看一下效果。

可以看到随着递归层级的加深，运算速度也在逐步减慢，有的时候甚至半天出不来一个结果了。

> [!danger]
>
> 因此我们在实际运用中，注意递归层级不要过深。



### 单词释义

| 单词               | 释义                                                   |
| ------------------ | ------------------------------------------------------ |
| Fibonacci sequence | 斐波那契数列，fib，seq为长单词短写，本身不是单词       |
| stack              | 栈，你可以理解为在一个容器中一块块放入木板，为加一层栈 |