1

Basically I have this huge function in Python (which I've simplified to the bare basics)

def rec(a,b):
  if stoppingCondition==True: return 1

  key=(a,b)
  if key in memo: return memo[key]

  if b==side condition:
       memo[key]=rec(a+1,b)   #RECURSIVE CALL
       return memo[key]

  total=0
  for d in D:
      if condition1==True:
          b=some process 1
          total+=rec(a+1,b)   #RECURSIVE CALL
      elif condition2==True:
          for x,y in d:
              if (some break condition==True): break
          else: #only gets called if break didnt happen
              b=some process 2
              total+=rec(a+1,b)   #RECURSIVE CALL
   memo[key]=total
   return memo[key]

And I am having a heck of a time making it iterative because it blows up for deeper recursive levels. I've already read up other threads about converting to loops and stacks and whatnot but I just can't get any of it working.

4

1 回答 1

1

您始终可以计算rec(a, b)all b，从最高点开始a并在一个简单的循环中递减而无需递归。现在，如果所有可能调用的遍历都是稀疏的，则此解决方案不可行rec()，因为它会引入许多不必要的计算。

另一种解决方案是尝试在 Python 中实现尾调用优化。我没试过，但你可能想测试这个装饰器。

一个不太优雅的解决方案是增加递归限制以满足您的需要：

import sys
sys.setrecursionlimit(10000)
于 2012-04-14T20:46:48.980 回答