Skip to main content

递归

必读

本课程网站内容请仔细阅读后再进行实操。因未仔细阅读内容，出现任何错误后果自负（逃～～～逃～～～逃

所有的代码请不要复制粘贴，请手敲每一行代码。复制粘贴不会让你动脑子，而手敲每一个行代码会让你自然而然地去动脑子会想每一行代码的含义和原理。所有的操作都需要自己动手，而不是立马就去问别人，只有自己动过脑子了才能学好。

递归函数​

如果函数的函数体直接或者间接自己调用自己，那么这个函数是递归的。递归是一种常见的数学和编程概念。它意味着函数调用自身。这样做的好处是可以循环访问数据以达成结果。

递归实现的阶乘函数案例

在cs201-learn的文件夹，用 VS Code 新建一个名字叫做 recursion01.py 的 Python 源代码文件。 输入如下代码，并运行

# -*- coding: utf-8 -*-

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

if __name__ == "__main__":
    factorial(10)

斐波那契函数案例

在cs201-learn的文件夹，用 VS Code 新建一个名字叫做 recursion02.py 的 Python 源代码文件。 输入如下代码，并运行

# -*- coding: utf-8 -*-

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

if __name__ == "__main__":
    fibonacci(6)
note

斐波那契数，又译为菲波拿契数、菲波那西数、斐氏数、黄金分割数。所形成的数列称为斐波那契数列，又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列。这个数列是由意大利数学家斐波那契在他的《算盘书》中提出。

在数学上，斐波那契数是以递归的方法来定义：

F0=1F1=1Fn=Fn−1+Fn−2(n≥2)\begin{align} & F_0 = 1 \\ & F_1 = 1 \\ & F_n = F_{n-1} + F_{n-2} (n \ge 2) \end{align}

递归求幂案例

在cs201-learn的文件夹，用 VS Code 新建一个名字叫做 recursion03.py 的 Python 源代码文件。 输入如下代码，并运行

# -*- coding: utf-8 -*-

def find_power(a, b):
    if b == 0:
        return 1
    else:
        return a * find_power(a, b-1)

if __name__ == "__main__":
    find_power(9, 3)

递归思想​

函数直接或者间接地调用自身。

递归有三大重点：

  • 第一要素：明确你这个函数想要干什么。
  • 第二要素：寻找递归结束条件。
  • 第三要素：找出函数的等价关系式。

第一要素

函数到底要实现什么功能是完全由你自己来定义的，比如说n的阶乘。

定义了一个函数：

def f(n):
    pass

第二要素

找出递归的结束条件，否则会一直调用自己。我们需要找出当参数，使递归结束，之后直接把结果返回，请注意！！！这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

接上面，当 n = 1 时，那你应该能够直接知道 f(n) 是什么？此时，f(1) = 1。完善函数内部的代码，把第二要素加进代码里面

# 算 n 的阶乘(假设n不为0)
def f(n):
    if n == 1:
        return 1
    # else:
    #     return n * f(n-1)

假设n为固定值，当n=10时，那想可以直接知道 f(n) 等于多少？那可以把n=10作为递归的结束条件

# 算 n 的阶乘(假设n>=10)
def f(n):
    if n == 10:
        return 10
    # else:
    #     return n * f(n-1)

注意我代码里面写的注释，假设 n>=10，因为如果 n=1 时，会被漏掉，当 n<=10 时，f(n)=n，所以为了更加严谨，我们可以写成这样：

# 算 n 的阶乘(假设n不为0)
def f(n):
    if n <= 10:
        return n
    # else:
    #     return n * f(n-1)

第三要素

找出函数的等价关系式。那么我们可以不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量，使原函数的结果不变。

f(n) 这个范围比较大，我们可以让 f(n) = nf(n-1)。这样，范围就由n变成了n-1了，范围变小了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以n。就是要找到原函数的一个等价关系式：f(n) = n f(n-1)。

f(5)
=>5*f(4)
=>5*(4*f(3))
=>5*(4*(3*f(2)))
=>5*(4*(3*(2*f(1))))
=>5*(4*(3*(2*1)))
=>5*(4*(3*2))
=>5*(4*6)
=>5*24
=>120

上面就显示了一个递归的流程。

什么时候用递归​

具有以下特征的问题可考虑递归求解：

  • 当问题和子问题具有递推关系，比如杨辉三角、阶乘。
  • 具有递归性质的数据结构，比如链表、树、图。
  • 反向性问题，比如取反。

层层拆解就可以使用递归。

尾递归​

以下面的阶乘为例

def factorial(n):  
    if n == 0:
        return 1
    return factorial(n - 1) * n

这个函数调用展开，会变成如下的形式：

factorial(4)  
factorial(3) * 4  
factorial(2) * 3 * 4  
factorial(1) * 2 * 3 * 4  
factorial(0) * 1 * 2 * 3 * 4  
1 * 1 * 2 * 3 * 4  
1 * 2 * 3 * 4  
2 * 3 * 4  
6 * 4  
24

可以看出，在每次递归调用的时候，都会产生一个临时变量，导致进程内存占用量增大一些。这样执行一些递归层数比较深的代码时，除了无畏的内存浪费，还有可能导致著名的堆栈溢出错误。

但是如果把上面的函数写成如下形式：

def factorial(n, acc=1):  
    if n == 0:
        return acc
    return factorial(n - 1, n * acc)

我们再脑内展开一下：

factorial(4, 1)  
factorial(3, 4)  
factorial(2, 12)  
factorial(1, 24)  
factorial(0, 24)  
24

很直观的就可以看出，这次的 factorial 函数在递归调用的时候不会产生一系列逐渐增多的中间变量了，而是将状态保存在 acc 这个变量中。而这种形式的递归，就叫做尾递归

尾递归的定义顾名思义，函数调用中最后返回的结果是单纯的递归函数调用（或返回结果）就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

在cs201-learn的文件夹，用 VS Code 新建一个名字叫做 recursion04.py 的 Python 源代码文件。 输入如下代码，并运行

# -*- coding: utf-8 -*-

def facttail(n, a):
     
    if n < 0:
        return 0;    
    elif n == 0:
        return 1;    
    elif n == 1:
        return a;
    else:
        return facttail(n - 1, n * a)

if __name__ == "__main__":
    facttail(10, 9)