python函数递归
9.6 函数的递归
在函数的内部，可以调⽤其他函数，函数内部调⽤⾃⼰，就是递归
前提条件：
1.函数⾃⼰调⽤⾃⼰
2.有终⽌条件
特点：
1.Python 递归函数 #必须有⼀个明确的结束条件；
编程递归函数2.每次进⼊更深⼀层递归时，问题规模相⽐上次递归都应有所减少
3.相邻两次重复之间有紧密的联系，前⼀次要为后⼀次做准备（通常前⼀次的输出就作为后⼀次的输⼊）。
4.递归效率不⾼，递归层次过多会导致栈溢出（在计算机中，函数调⽤是通过栈（stack）这种数据结构实现的，每当进⼊⼀个函数调⽤，栈就会加⼀层栈帧，每当函数返回，栈就会减⼀层栈帧。由于栈的⼤⼩不是⽆限的，所以，递归调⽤的次数过多，会导致栈溢出
练习：(利⽤递归)
n!
fact(n) = n!
递归会有栈溢出现象，那么这种现象怎么解决？
解决递归调⽤栈溢出的⽅法是通过尾递归优化，事实上尾递归和循环的效果是⼀样的，所以，把循环看成是⼀种特殊的尾递归函数也是可以的。
尾递归是指，在函数返回的时候，调⽤⾃⾝本⾝，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本⾝⽆论调⽤多少次，都只占⽤⼀个栈帧，不会出现栈溢出的情况。
上⾯的fact(n)函数由于return n * fact(n - 1)引⼊了乘法表达式，所以就不是尾递归了。要改成尾递归⽅式，需要多⼀点代码，主要是要把每⼀步的乘积传⼊到递归函数中：
def fact(n):
return fact_iter(n, 1)
def fact_iter(num, product):
if num == 1:
return product
return fact_iter(num - 1, num * product)
可以看到，return fact_iter(num - 1, num * product)仅返回递归函数本⾝，num - 1和num * product在函数调⽤前就会被计算，不影响函数调⽤。
fact(5)对应的fact_iter(5, 1)的调⽤如下
===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120
尾递归调⽤时，如果做了优化，栈不会增长，因此，⽆论多少次调⽤也不会导致栈溢出。
遗憾的是，⼤多数编程语⾔没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上⾯的fact(n)函数改成尾递归⽅式，也会导致栈溢出。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。