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老爹拒绝尾递归优化的理由

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 函数名其实就是指向一个函数对象的引用,完全可以把函数名赋给一个变量,相当于给这个函数起了一个“别名”:a = ab...
    bjchenli阅读 631评论 0 0
  • 基础1.r''表示''内部的字符串默认不转义2.'''...'''表示多行内容3. 布尔值:True、False(...
    neo已经被使用阅读 1,714评论 0 5
  • 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n!...
    小呀小芒果阅读 4,049评论 0 0
  • 函数### 函数名其实就是指向一个函数对象的引用,完全可以把函数名赋给一个变量,相当于给这个函数起了一个“别名”:...
    MJXH阅读 1,112评论 0 0
  • 你一次次启程,突破所有过去的边界,走向一切未知的领域。你不知道下一个转角会遇见什么,但只要内心澄澈,一切都是惊喜。
    小芳兜兜阅读 195评论 0 0