python笔记-递归函数

递归

在一个函数内部,调用它自身,我们就称之为递归函数(recursive function)

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

这是一个很经典的递归函数:计算n的阶乘.函数的调用是通过栈(stack)的数据结构实现的,如下:

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

每进入一个函数调用,栈就会加一层栈帧,每当一个函数返回,就会减少一层栈帧,它会一直调用到没得继续往下调后才会开始一层层返回,因为递归函数有栈溢出的风险,为了避免溢出,可以使用尾递归

尾递归

在使用递归函数时,return语句不能包含表达式,这样编译器或解释器就可以把尾递归做优化,是递归不论多少次都只占用一个栈帧

事实上尾递归和循环效果一样,把循环堪称以一种特殊的尾递归函数也是可以的.

# 把上面的阶乘函数改成尾递归
def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

# 通过fact函数触发
def fact(n):
    return fct_iter(n)

num-1和num*product作为参数,在函数调用前就会被计算,过程如下:

===> fact(5)
===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120

相当于每一次都把前面的值算出来,再进入下一轮调用,从而避免栈溢出.

然而

遗憾的是,Python标准解释器没有对尾递归做优化,所以任何递归函数都存在栈溢出问题,所以这个知道就好.