学习目标

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标准的解释器没有针对尾递归做优化，所以任何递归函数都存在栈溢出的问题。