从 Python 2.6 到 2.7 时深度递归的分段错误

Question

我有一个简单的递归程序来查找连接的子图。该代码的工作原理是，从图形中的每个未访问的顶点遍历所有边(递归(，并在此过程中用"ingraph=False"标记已访问的边。(图形始终是无向未加权的图形(。

我遇到的问题是，对于大型图(子图为 ~100,000 个顶点(，python(-2.7( 返回分割错误。但这在 python-2.6 中工作得很好(现在仍然如此(。

有人可以向我解释两个之间发生了什么变化(或者可能完全是其他东西(？有没有办法用python-2.7修复它(最好在某个时候迁移到python-3时也不会中断(？还是我应该以非递归的方式重写它？

谢谢！

这是源更新：有关非递归解决方案，请参阅下面的更新 3

def floodfill(g):
  for v in g.vertices: v.ingraph = True
  sys.setrecursionlimit(g.size)
  subgraph = 1
  for v in g.vertices:
    if v.ingraph:
      v.ingraph = False
      v.subgraph = subgraph
      g.floodfill_search(v,subgraph)
      subgraph += 1
def floodfill_search(g,v,subgraph):
  for n in v.neighbors:
    if n.ingraph:
      n.ingraph = False
      n.subgraph = subgraph
      g.floodfill_search(n,subgraph)

------更新--------

我做了一个小的递归测试，它给出了 3 台不同计算机的递归限制为 ~16,000、~24,000 和 ~28,000。此外，对于一台电脑来说，结果甚至不是恒定的。运行两次测试给出的限制略有不同。例如，对于第二个，我找到 23800 和 23819 之间的结果。

#!/usr/bin/python
import sys
def callme(i):
  print(i)
  i+=1
  callme(i)
sys.setrecursionlimit(int(1e6))
callme(0)

我真的不明白指的是哪个"C 堆栈"，据我所知，C 中没有实现默认的"堆栈"。在C++中，有堆栈，但它没有相同的限制。以下C++示例运行良好(至少最多 1M 次推送(。

#include <iostream>   
#include <stack>
using namespace std;
int main () {
  stack<int> s;
  for(int i=0;i<1000000;i++) {
    cout << "push " << i << endl;
    s.push(i);
  }
}

下面的 C 代码也更深入(大约 10x，~262,000(

#include "stdio.h"
void callme(i) { 
  printf("calling %dn",i);
  callme(++i);
}
int main() {
  int i=0;
  callme(i);
}

----更新 2 -----

好吧，这显然是蟒蛇的意图。迫使程序员避免深度递归。http://neopythonic.blogspot.ch/2009/04/tail-recursion-elimination.html

无论如何，我现在认为最好迭代重写它。但是，我可能会在C++重新开始，使用一些图论库，如提升图库。如果无论如何我都必须重写它，我不妨正确地重写它。

尽管如此，我仍然希望有任何评论，以了解为什么在这些特定尺寸下会发生这种情况。

----更新 3 -----

这里至少是一个快速而肮脏的 python 重写。脏，因为它是 O(N^2(，因为最后一行。应该有一个更好的 O(N( 解决方案，通过跟踪哪些顶点没有被访问过，但没有这么快看到它的列表，这对我的应用程序有效。

def floodfill_nonrecursive(g):
    for v in g.vertices: v.ingraph = True
    start = g.vertices
    subg = 1
    while start:
      q = [start[0]]
      while q:
        v = q.pop()
        v.ingraph = False
        v.subgraph = subg
        for n in v.neighbors:
          if n.ingraph:
            n.ingraph = False
            q.append(n)
      subg += 1
      start = [v for v in g.vertices if v.ingraph]

Answer 1

因为你的Python使用C堆栈，所以它是溢出的。 setrecursionlimit无法扩展堆栈大小。它只是限制在 cstack 溢出之前引发异常。Python的递归深度有限。在 2.6 中取得成功只是幸运的情况。

你应该把你的代码从递归改为迭代风格，或者使用无栈python(或PyPy(。阅读 http://docs.python.org/2/library/sys.html#sys.setrecursionlimit

Answer 2

你可能在 Python 实现中的某个地方溢出了深度递归的堆栈。您可以尝试使用 sys.setrecursionlimit 更改堆栈部门

另一种可能性是耗尽动态内存。递归通常更费力。

你在Python 2.6上有更多的运气。以前的版本需要较少的内存用于您的算法。

Python 不是一种函数式语言，不会优化尾递归。迭代重写算法可能是一种更好的方法。