4.递归

作者: WandaGao | 来源:发表于2022-03-03 12:29 被阅读0次

4.递归
数据结构学习笔记：二分搜索树
数据结构----递归
算法2：递归算法与二分查找
10.正则表达式匹配
4. 函数和递归
快速排序
斐波那契数列与Python的尾递归蹦床　连载【2】
FTP
2020-08-21 算法合集

首先所有的递归都可以使用循环来替代
递归并不是一种高性能解决问题的方式，但使用递归可以使代码更易于理解与阅读，更优雅

1.什么是递归？
函数调用自身就可以称为递归
递归需要：基线条件和递归条件，尤其是基线条件，否则自身调用将陷入无限循环

def cutDown(i):
    print(i)
    cutDown(i - 1)


if __name__ == '__main__':
    cutDown(10)

#以下是错误日志（当print打印到 -993时 报错，栈溢出）
[Previous line repeated 993 more times]
  File "E:/python/pythonProject1/递归.py", line 2, in cutDown
    print(i)
RecursionError: maximum recursion depth exceeded while calling a Python object

上述代码由于缺少基线条件导致，无限循环

def cutDown(i):
    if i < 0:   # 当i<0时 退出递归
        return
    else:
        print(i)
        cutDown(i - 1)


if __name__ == '__main__':
    cutDown(10)

上述代码中 i<0 return 即为基线条件用来终止递归循环
else 即为递归条件用来表明何时进行递归调用

2.栈
数据结构中的一种，特点是有序且后进先出（栈顶优先），例如弹夹
在计算机中使用的栈是调用栈
一般来讲它主要负责程序的执行（处理函数的执行，以及记录函数中的局部变量，参数，中间计算过程等状态），它以栈的形式来管理函数执行，每当执行函数时，就会压入一个栈帧（记录并执行函数），函数执行完毕，就会执行出栈，修改栈帧，把压入的内容销毁

举例：

def greet(name):
    print('hello,' + name + "!")
    greet2('maggie')
    print("getting ready to say bye。。。")
    bye()


def greet2(name):
    print("how are you")


def bye():
    print("ok bye!")


if __name__ == '__main__':
    greet('maggie')

其实print也是一个函数，但这里暂时忽略它

当我们调用 greet('maggie')，计算机就会首先为函数调用分配一块内存

image.png

我们使用这些内存，变量name 被设置为ning 这需要存储在内存中

image.png

*每个函数调用时，计算机就会分配内存将，以栈的形式，将函数压入栈中，将调函数涉及的所有变量的值存储在内存中。

接下来打印hello，maggie！在调用greet2（'maggie'）,同样 greet2（'maggie'）被分配内存压入栈中。

栈顶

栈底

*栈的优先级为后进先出，因此栈顶的Greet2（）将会执行，栈底的greet（）将停止执行并等待。

接着执行Greet2（）打印 how are you , maggie?
Gree2() 执行完毕栈顶的Greet2（）执行出栈，释放内存，并返回 greet（）

greet2（）出栈

此时，greet（）处于栈顶，由等待转换为继续执行，打印getting ready to say bye。。。

接着执行bye()方法， bye（）被压入栈顶，greet()暂停执行

bye（）方法处于栈顶

执行bye（）打印 ok bye! ，bye （）执行完毕，进行出栈，释放内存，并返回 greet（）

bye()出栈，greet()成为栈顶

greet() 接着执行完毕，greet() 进行出栈，释放内存

这个存储多个函数数据，状态的栈被称为调用栈，调用栈遵循栈顶优先原则

3.递归调用栈
递归函数也是用调用栈！我们来分析下阶乘算法 n!(5! =54321)

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

接下来我们来分析 factorial(3)的执行

当执行 factorial(3) 时，将fac（3）压入栈， 3！=1 所以执行 else:
执行 $3*fac（3-1）$
这里进行递归再次调用 fac() 函数，只不过参数为2 即 fac(2)
fac(2) 压入栈顶执行，fac(3) 暂停， 2！=1 所以执行 else $2*fac(2-1)$
进行递归调用 fac（2-1）即fac（1）
fac(1) 压入栈顶执行，fac(2) 暂停，1==1 所以执行return 1

fac(1)执行完毕，出栈，并返回值1
返回fac（2）继续执行中断位置 $2*fac（1）$ 即为 $2*1$ ，执行reutn 2
fac(2) 执行完毕，出栈，并返回值2
返回fac(3)，继续执行 $3*fac（2）$ 即 $3*2$ ，执行return 6
fac(3)执行完毕，出栈，并返回值 6