学习目标
1、掌握递归函数的使用。
2、理解尾递归优化。
递归函数
在函数内部可以调用其他函数,如果函数内部调用自身,则这个函数就是递归函数。
计算阶乘n!=1x2x3x...x(n-1)xn,用fact(n)表示
fact(n)=n!=1x2x3x...x(n-1)xn=(n-1)!xn=fact(n-1)xn
因此fact(n)=nxfact(n-1)
def fact(n):
if n==1 :
return 1
return n * fact(n-1)
print(fact(5))
print(fact(100))
print(fact(1000)) #栈溢出
递归函数的优点是定义简单、逻辑清晰,但是使用递归函数需要注意防止栈溢出。解决递归调用栈溢出的方法是尾递归优化,尾递归是指函数返回时调用本身且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)
print(fact(5))
print(fact(100))
print(fact(1000)) #栈溢出
Python标准的解释器没有针对尾递归做优化,所以任何递归函数都存在栈溢出的问题。