Python函数 — 递归函数
1、什么是递归函数
Python中递归函数是指在函数内部调用自身的函数。递归函数通常用来解决需要重复执行相同操作的问题。
2、递归函数的优缺点
优点：
- 递归函数实现简单，易于理解；
- 适合解决相对简单、结构严谨的问题；
- 代码相对紧凑、优美。
缺点：
- 递归函数调用过程中会多次压栈、弹栈，对内存和运行效率的损耗较大；
- 当递归层数过多时会导致栈溢出；
- 递归实现，根据递归的方式不同，时间复杂度和空间复杂度有可能会变得非常高，不太适合处理大规模的数据。
3、如何设计递归函数
Python中编写递归函数，可以按照以下步骤进行：
（1）确定终止条件，递归函数必须有终止条件，否则递归将永远不会结束。
（2）拆分问题，把原问题拆分成多个相同的子问题，每个子问题的计算方式与原问题相同，只是规模或参数有所不同。
（3）调用自身，递归函数在自身内部调用自身来解决每个子问题。
（4）合并结果，将子问题的结果合并起来得到原问题的解。
4、递归函数的应用示例
（1）计算阶乘
# 计算n的阶乘
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)（2）计算斐波那契数列
# 计算斐波那契数列第n项的值
def fib(n):
if n <= 1:
return n
else:
return fib(n - 1) + fib(n - 2)
# 打印斐波那契数列
def test(x):
lst = []
for i in range(x):
lst.append(fib(i))
return lst
print(test(10))reference：
递归函数 | 酷python