专栏首页PythonPython中的栈溢出及解决办法

Python中的栈溢出及解决办法

1.递归函数

在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。

举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出:

fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n

所以,fact(n)可以表示为n x fact(n-1),只有n=1时需要特殊处理。

于是,fact(n)用递归的方式写出来就是:

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

上面就是一个递归函数。可以试试:

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

如果我们计算fact(5),可以根据函数定义看到计算过程如下:

===> 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

递归函数的优点是定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。

使用递归函数需要注意防止栈溢出。

2.栈溢出

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

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded

 尾递归

解决递归调用栈溢出的方法是通过尾递归优化,事实上尾递归和循环的效果是一样的,所以,把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。

上面的fact(n)函数由于return n * fact(n - 1)引入了乘法表达式,所以就不是尾递归了。要改成尾递归方式,需要多一点代码,主要是要把每一步的乘积传入到递归函数中:

def fact(n):
    return fact_iter(1, 1, n)

def fact_iter(product, count, max):
    if count > max:
        return product
    return fact_iter(product * count, count + 1, max)

可以看到,return fact_iter(product * count, count + 1, max)仅返回递归函数本身,product * countcount + 1在函数调用前就会被计算,不影响函数调用。

fact(5)对应的fact_iter(1, 1, 5)的调用如下:

===> fact_iter(1, 1, 5)
===> fact_iter(1, 2, 5)
===> fact_iter(2, 3, 5)
===> fact_iter(6, 4, 5)
===> fact_iter(24, 5, 5)
===> fact_iter(120, 6, 5)
===> 120

尾递归调用时,如果做了优化,栈不会增长,因此,无论多少次调用也不会导致栈溢出。

遗憾的是,大多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以,即使把上面的fact(n)函数改成尾递归方式,也会导致栈溢出。

优化尾递归的装饰器

有一个针对尾递归优化的decorator,可以参考源码:

#!/usr/bin/env python2.4
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is 
# it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
  def __init__(self, args, kwargs):
    self.args = args
    self.kwargs = kwargs

def tail_call_optimized(g):
  """
  This function decorates a function with tail call
  optimization. It does this by throwing an exception
  if it is it's own grandparent, and catching such
  exceptions to fake the tail call optimization.
  
  This function fails if the decorated
  function recurses in a non-tail context.
  """
  def func(*args, **kwargs):
    f = sys._getframe()
    if f.f_back and f.f_back.f_back \
        and f.f_back.f_back.f_code == f.f_code:
      raise TailRecurseException(args, kwargs)
    else:
      while 1:
        try:
          return g(*args, **kwargs)
        except TailRecurseException, e:
          args = e.args
          kwargs = e.kwargs
  func.__doc__ = g.__doc__
  return func

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

现在,只需要使用这个@tail_call_optimized,就可以顺利计算出fact(1000)

>>> fact(1000)
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048
0047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950
5950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476
6328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791
4385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155
8611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151
0273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215
6683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535
3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200
0158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760
8850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403
1274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786
9061172601587835207515162842255402651704833042261439742869330616908979684825901254583271682264580665
2676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946
5955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657
2450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623
7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179
9702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819
3723886426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233
4482801505139969429015348307764456909907315243327828826986460278986432113908350621709500259738986355
4277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994
8717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636
7740459574178516082923013535808184009699637252423056085590370062427124341690900415369010593398383577
7939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python标准库(1) — itertools模块

    目录[-] 简介 官方描述:Functional tools for creating and using iterators.即用于创建高效迭代器的函数。...

    jhao104
  • Pycharm创建virtualenv方法

    目录[-] Python的版本众多,在加上适用不同版本的Python Package。这导致在同时进行几个项目时,对库的依赖存在很大的问题。这个时候就牵涉...

    jhao104
  • 在Python应用中使用MongoDB

    目录[-] Python是开发社区中用于许多不同类型应用的强大编程语言。很多人都知道它是可以处理几乎任何任务的灵活语言。因此,在Python应用中需要一个...

    jhao104
  • Python魔术方法-Magic Method

    目录[-] 介绍 在Python中,所有以“__”双下划线包起来的方法,都统称为“Magic Method”,例如类的初始化方法 __init__ ,Pyt...

    jhao104
  • Python正则表达式:最短匹配

    目录[-] 最短匹配应用于:假如有一段文本,你只想匹配最短的可能,而不是最长。 例子 比如有一段html片段,<a>this is first label<...

    jhao104
  • Python检查xpath和csspath表达式是否合法

    目录[-] 在做一个可视化配置爬虫项目时,需要配置爬虫的用户自己输入xpath和csspath路径以提取数据或做浏览器操作。考虑到用户的有时会输入错误的x...

    jhao104
  • 博客群发(1)--构思

    博客群发 最近想把博客发到多个博客里去,发现现在网上很多软件都是收费的,而且效果怎么样也不清楚,于是有了这个想法,想做一个博客群发的软件,基本的语言使用的是py...

    cloudskyme
  • Python标准库笔记(3) — datetime模块

    目录[-] datetime模块提供了简单和复杂的方式用于操纵日期和时间的类。虽然支持日期和时间运算,但实现的重点是为了输出格式化和操作高效地提取属性。 ...

    jhao104
  • Python爬虫代理IP池

    目录[-] 在公司做分布式深网爬虫,搭建了一套稳定的代理池服务,为上千个爬虫提供有效的代理,保证各个爬虫拿到的都是对应网站有效的代理IP,从而保证爬虫快速...

    jhao104
  • 博客群发(2)--实现登陆

    模板方法 python也是一种面向对象的语言,所以在实现群发的时候,会登陆不同的网站,但是登陆的方法什么的不尽相同,所以这里想到的是模板方法。 模板方法模式: ...

    cloudskyme

扫码关注云+社区

领取腾讯云代金券