python 递归函数 栈溢出

题目：

计算阶乘n!=n*(n-1)*(n-2)*…3*2*1

用递归函数来表示为：

def f(x):

   if x==1:

       return 1

   return x*f(x-1)

代码截图 运行结果

计算5的阶乘5！，运行正确。

接着计算大一点的数1000！：

代码截图 运行结果 运行结果

可以看到运行结果报错了，这是因为出现了栈溢出。

在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

在计算1000！时，递归函数使得函数调用次数非常多，层级很深，返回却很少，导致堆栈无法容纳大量的调用返回地址，从而产生溢出。

解决思路是：

对return语句进行尾递归优化，也就是避免在return语句里出现表达式（上文代码中的‘return x*f(x-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)

上文代码是做了尾递归优化的情形，可惜的是python并不支持尾递归优化，python递归的次数在1000以内不会产生溢出，1000以上就要考虑用循环来代替了。

可修改成：

def function(x):

    s = 1

    if x == 1:

        return 1

    if x>1:

        for i in range(1,x+1):

            s = s*i

         return s

    else:

        return 'No Answer!'

print function(5)

代码截图 运行结果

print function(1000)已经可以正常输出了。

案例及学习材料来源：廖雪峰大大的博客

扩展阅读：python老爹拒绝尾递归优化的理由