首先所有的递归都可以使用循环来替代
递归并不是一种高性能解决问题的方式，但使用递归可以使代码更易于理解与阅读，更优雅
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:
执行
这里进行递归 再次调用 fac() 函数，只不过参数为2 即 fac(2)
fac(2) 压入栈顶执行，fac(3) 暂停， 2！=1 所以执行 else
进行递归调用 fac（2-1）即fac（1）
fac(1) 压入栈顶执行，fac(2) 暂停，1==1 所以执行return 1
fac(1)执行完毕 ，出栈，并返回值1
返回fac（2） 继续执行中断位置 即为
，执行reutn 2
fac(2) 执行完毕，出栈，并返回值2
返回fac(3)，继续执行 即
，执行return 6
fac(3)执行完毕，出栈，并返回值 6
*每个fac()调用都有自己x变量，在一个函数调用中不能访问另一个x的变量
总结
递归是指函数调用自己
每个递归函数都要有两个条件：基线条件，递归条件
栈有两种操作：压入和弹出
所以函数都进入调用
调用栈可能很长，这将占用大量内存
网友评论