1 递归定义
函数直接或间接调用函数本身，则该函数称为递归函数
2 递归特点
Python函数递归调用，会用到栈
– 这里的栈是函数/程序运行时系统为其分配的一段内存区
– 栈具有 后进先出 的特性
– 该段内存区域大小有限，大小跟系统有关
– 该区用来存储局部变量等
– 递归函数，调用时借助这个区域存放中间过程
– 所以递归有层数限制
3 优缺点
优点：把问题简单化，让逻辑调理清晰
缺点：递归是一种运行效率不高的调用方式，消耗很多系统资源；一般的编程语言对递归的层数有一定的限制
4 递归函数的设计
递推阶段：从原问题出发，按照递归的调用方法逐渐推进，从未知到已知，直到终止条件
回归阶段：按照终止条件求出结果，逐层的回归带入原问题
终止条件： 一定要有终止条件 ，并且终止一定出现在函数的内部调用之前
5 实现递归函数
如：计算整数n的阶层
循环：
def fact(n): r = 1 i = 1 while i <= n: r = r * i i = i + 1 return r a = fact(5) print(a)
递归：
def fact(n): if n == 1: return 1 else: return n * fact(n - 1) a = fact(5) print(a)
5.1计算阶层递归的执行过程解析
fact(5)
1、5 * fact(4) 2、5 * (4 * fact(3)) 3、5 * (4 * (3 * fact(2))) 4、5 * (4 * (3 * (2 * fact(1))))
5、5 * (4 * (3 * (2 * 1))) 6、5 * (4 * (3 * 2)) 7、5 * (4 * 6) 8、5 * 24 9、120
6 小结
• 使用递归必须有一个终止条件
• 使用递归优点——实现简单，结构清晰
• 理论上递归都可以用循环来实现
• 递归要防止栈溢出，有调用层数限制