> 文档中心 > 【Python数据结构与算法】(三):递归(Recursion)

【Python数据结构与算法】(三):递归(Recursion)


【Python数据结构与算法】(三):递归(Recursion)

  • ✨本文收录于《Python数据结构与算法》专栏,此专栏主要记录如何python学习数据结构与算法笔记。
  • 🌸个人主页:JoJo的数据分析历险记
  • 📝个人介绍:小编大四统计在读,目前保研到统计学top3高校继续攻读统计研究生
  • 💌如果文章对你有帮助,欢迎✌关注、👍点赞、✌收藏、👍订阅专栏

文章目录

  • 【Python数据结构与算法】(三):递归(Recursion)
  • 1.递归基本概念
  • 应用一:阶乘计算
  • 应用二:斐波那契数列
  • 应用三:汉诺塔问题
  • 2.递归VS.迭代
    • 2.1 区别和联系
    • 2.2 如何选择

1.递归基本概念

递归函数本质上是一直调用自身的函数。其基本思想把要解决的问题转化为一个子问题,而这个子问题的解决方法仍与原来的解决方法相同,只是问题的规模变小了。其基本特点如下:

  • 调用自身:例如f ( n ) = f ( n − 1 ) + 1 f(n)=f(n-1)+1 f(n)=f(n1)+1
  • 结束条件:如果没有结束条件,那么会进入死循环

就像大家在高中学过的数学归纳法一样,我们要有一个基础值,然后分析 f ( n ) 和 f ( n + 1 ) f(n)和f(n+1) f(n)f(n+1)之间的关系。因此,我们在写递归时,首先要确定我们的结束条件。

可以看出来递归有点类似我们的循环迭代。我们来介绍几个具体案例来理解一下递归和迭代的区别和联系:

应用一:阶乘计算

首先我们来明确阶乘的基本特性

n ! = n ( n − 1 ) . . . 2 × 1 n ! = n ( n − 1 ) ! 0 ! = 1 n!=n(n-1)...2\times1\hspace{10cm}\\ n!=n(n-1)!\hspace{10cm}\\ 0!=1 \hspace{10cm} n!=n(n1)...2×1n!=n(n1)!0!=1

例如 3 ! = 3 × 2 × 1 = 6 3!=3\times2\times1=6 3!=3×2×1=6

方法一:使用for循环

根据上面的分析,我们编写一个for循环代码,具体如下:

def factorial(n):    result = 1#初始值    for i in range(1, n+1):#1到n result *= i#累乘    return result

使用for循环的时间复杂度为O(n)

方法二:使用递归

因此我们可以很轻易的写出它的调用关系和结束条件:

  • 调用自身:调用的关系n ! = n ( n − 1 ) ! n!=n(n-1)! n!=n(n1)!
  • 结束条件:0 ! = 1 0!=1 0!=1

下面我们来看具体代码:

def factorial(n):    """结束条件,如果n为0,则返回1,此时不再调用自身"""    if n == 0: return 1    """调用自身"""    return n*factorial(n-1)factorial(4)
24

其具体计算步骤如下图所示:

image-20220605002708722

首先,不断调用自身,直到为0后,停止调用自身,返回1;然后得出我们的阶乘值。
下面我们通过这个动图求解 f i b ( 5 ) fib(5) fib(5)来进一步理解:
阶乘
接下来我们来分析一下它的时间复杂度:每次调用自身都是一个操作,因此上述我们计算阶乘的时间复杂度是: O ( n ) O(n) O(n)

注意:我们在使用递归时候,每一次递归都会占用内存,在python中,因此在实际中使用递归时候,调用次数不要太多了,一般1000以内是没有问题的。

这样来看,使用递归还不如我们之前的for循环,但是在有的问题,for循环不好处理,而递归能较好的完成这些问题。因此,我们还是有必要了解递归这个思想的

应用二:斐波那契数列

斐波那契数列是一个非常经典的递归问题,具体值如下:

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21... 1,1,2,3,5,8,13,21... 1,1,2,3,5,8,13,21...
具体计算过程如下所示:
斐波那契数量
我们可以看出每一项的值等于前两项的和,前两项的值为1。因此我们不难得出

  • 结束条件:f ( 1 ) = f ( 2 ) = 1 f(1)=f(2)=1 f(1)=f(2)=1
  • 调用自身关系:f ( n ) = f ( n − 1 ) + f ( n − 2 ) , n > 2 f(n)=f(n-1)+f(n-2),n>2 f(n)=f(n1)+f(n2),n>2
方法一:使用递归

下面实现具体递归代码:

def fib(n):    assert n>0#确保n是大于0的    if n<=2: return 1    return fib(n-1) + fib(n-2)

现在我们来分析一下它的时间复杂度。大家可以画成一个二叉树的形式,所以它的时间复杂度是 O ( 2 n ) O(2^n) O(2n).

方法二:下面我们看一下for循环是如何写的
def fib2(n):    assert n>0    a,b = 0, 1    for i in range(1, n+1): a,b = b, a+b    return a

经过之前的分析,我们知道使用for循环的时间复杂度是 O ( n ) O(n) O(n),也比我们之前的递归写法要快很多。

为什么要研究斐波那契数列呢?下面我们用每一项除以它的前一项,具体代码如下

fibos = fibonaccis(15)r = []for i in range(2, len(fibos)):    r.append(fibos[i] / fibos[i-1])r
[1.0, 2.0, 1.5, 1.6666666666666667, 1.6, 1.625, 1.6153846153846154, 1.619047619047619, 1.6176470588235294, 1.6181818181818182, 1.6179775280898876, 1.6180555555555556, 1.6180257510729614]

从结果来看,我们发现返回值趋近于1.618,这不就是黄金比例+1嘛,在自然界中,也有许多类似斐波那契数列的事物。

应用三:汉诺塔问题

大家小时候可能都玩过汉诺塔,具体如下图所示:

image-20220605135823137

一共有三根柱子,的第一个柱子上,从下往上安装大小顺序排列。现在我们要求将圆盘按大小顺序重新排放在另一根柱子上。

  • 每次只能从上面开始移动一个圆盘
  • 小圆盘上面不能放大圆盘,只能放比它更小的圆盘。

现在假设我们想要将圆盘从A移动到C(因为C和B其实是等价的)。那么具体如何操作呢

一:首先我们来看两个圆盘的情况
  • 将A的小圆盘移动到B
  • 再将A大圆盘移动到C
  • 再将小圆盘从B移动到C
二:n个圆盘的情况
  • 首先将n-1个圆盘从A经过C移动到B
  • 将第n个圆盘从A移动到C
  • 将n-1个圆盘从B经过A移动到C

可以看出,汉诺塔是一个非常经典的递归问题。结束条件是n=0,没有盘子说明我们不需要移动,下面我们来看看如何写具体的代码

def hanoi(n,A,B,C):    if n>0: hanoi(n-1,A,C,B)#将n-1个小圆盘从A经过C移动到B print('Moving from'+A+'to'+C)#将大圆盘从A移动到C hanoi(n-1,B,A,C)#将n-1个小圆盘从B经过A移动到C hanoi(3,'A','B','C')
Moving from A to CMoving from A to BMoving from C to BMoving from A to CMoving from B to AMoving from B to CMoving from A to C

大家可以看出三个圆盘需要移动七次,顺序为
A-C,A-B,B-C,A-C,B-A,B-C,A-C

通过这些经典应用案例,我相信大家已经比较理解递归,在我们了解递归之后。我们接下来比较一下递归和迭代。

2.递归VS.迭代

2.1 区别和联系

  • 递归和迭代执行相同任务:一次解决一个复杂的任务,并将结果结合起来
  • 迭代的重点:不断重复,一直到完成问题。
  • 递归的重点:解决一个大问题,把它分解成更小更小的部分。因此,关键在于找到调用自身的关系和结束条件

2.2 如何选择

关于如何选择递归和迭代。没有一个明确的答案。取决于我们具体要解决的问题。例如在很多ADT中,使用递归可能会更简单。但是要注意,使用递归通常的时间复杂度会比迭代大。

在这里插入图片描述
本章的介绍到此介绍,如果文章对你有帮助,请多多点赞、收藏、评论、关注支持!!