如何使这个方法非递归？

Question

嘿。这个例子非常具体，但我认为它可以应用于广泛的功能。 它来自一些在线编程比赛。

有一个简单的获胜条件的游戏。平局是不可能的。游戏不能永远持续下去，因为每一步都会让你更接近终止条件。在给定状态的情况下，该功能应该确定现在要移动的玩家是否具有获胜策略。 在该示例中，状态是一个整数。玩家选择一个非零数字并从数字中减去：新的状态是新的整数。胜利者是达到零的玩家。

我这个编码：

from Memoize import Memoize 

@Memoize 
def Game(x): 
    if x == 0: return True 
    for digit in str(x): 
     if digit != '0' and not Game(x-int(digit)): 
      return True 
    return False 

我想很明显它是如何工作的。我也意识到，对于这个特定的游戏可能有一个更聪明的解决方案，但我的问题是一般的。然而，即使对于相对较小的输入，这也会使python变得疯狂。有没有什么办法让这段代码在循环中工作？

感谢

这就是我的意思翻译成一个循环：

def fac(x): 
    if x <= 1: return x 
    else: return x*fac(x-1) 

def fac_loop(x): 
    result = 1 
    for i in xrange(1,x+1): 
     result *= i 
    return result 

## dont try: fac(10000) 
print fac_loop(10000) % 100 ## works 

Answer 1

一般来说，只有在递归函数为primitive-recursive时，才有可能将递归函数转换为循环;这基本上意味着他们只在体内自称一次。你的函数自动调用多次。这样的功能确实需要一个堆栈。可以使堆栈显式化，例如，与列表。使用一个明确的堆栈你的算法的一个再形成是

def Game(x): 
    # x, str(x), position 
    stack = [(x,str(x),0)] 
    # return value 
    res = None 

    while stack: 
     if res is not None: 
      # we have a return value 
      if not res: 
       stack.pop() 
       res = True 
       continue 
      # res is True, continue to search 
      res = None 
     x, s, pos = stack.pop() 
     if x == 0: 
      res = True 
      continue 
     if pos == len(s): 
      # end of loop, return False 
      res = False 
      continue 
     stack.append((x,s,pos+1)) 
     digit = s[pos] 
     if digit == '0': 
      continue 
     x -= int(digit) 
     # recurse, starting with position 0 
     stack.append((x,str(x),0)) 

    return res 

基本上，你需要将每一种局部变量堆栈帧的元素;这里的局部变量是x，str（x）和循环的迭代计数器。做返回值有点棘手 - 如果函数刚刚返回，我选择将res设置为not-None。

Answer 2

通过“发疯”我想你的意思是：

>>> Game(10000) 
# stuff skipped 
RuntimeError: maximum recursion depth exceeded in cmp 

你可以在底部启动相反 - 一个粗略的变化将是：

# after defining Game() 
for i in range(10000): 
    Game(i) 

# Now this will work: 
print Game(10000) 

这是因为，如果你从一个很高的数字开始，在到达底部（0）之前你需要经过很长的一段时间，所以你的memoization装饰器没有帮助它。

通过从底部开始，确保每次递归调用都立即触碰结果字典。你可能会使用额外的空间，但是你不会远虑。

您可以使用循环和堆栈将任何递归函数转换为迭代函数 - 本质上是手动运行调用堆栈。例如，参见this question或this quesstion进行一些讨论。这里可能有一个更优雅的基于循环的解决方案，但它不会跳到我身上。

Answer 3

那么，递归主要是关于能够执行一些代码而不会丢失先前的上下文和顺序。特别是，函数框架在递归期间放入并保存到调用堆栈中，因此由于堆栈大小有限而给予递归深度约束。您可以通过在堆内存上创建状态堆栈，手动管理/保存每次递归调用所需的信息来“增加”递归深度。通常，可用堆内存的数量大于堆栈的数量。认为：良好的快速排序实现通过创建具有不断变化的状态变量的外部循环（在QS示例中为下部/上部数组边界和枢轴）来消除向较大侧的递归。

当我打字时，Martin v。Löwis发表了关于将递归函数转换为循环的良好答案。

Answer 4

您可以修改您的递归版本有点：

def Game(x): 
    if x == 0: return True 
    s = set(digit for digit in str(x) if digit != '0') 
    return any(not Game(x-int(digit)) for digit in s) 

这样，你不检查位数多次。例如，如果你在做111，你不必三次看110。

我不知道这是否算作你提出的原始算法的迭代版本，但这里是一个memoized迭代版本：

import Queue 
def Game2(x): 
    memo = {} 
    memo[0] = True 
    calc_dep = {} 
    must_calc = Queue.Queue() 
    must_calc.put(x) 
    while not must_calc.empty(): 
     n = must_calc.get() 
     if n and n not in calc_dep: 
      s = set(int(c) for c in str(n) if c != '0') 
      elems = [n - digit for digit in s] 
      calc_dep[n] = elems 
      for new_elem in elems: 
       if new_elem not in calc_dep: 
        must_calc.put(new_elem) 
    for k in sorted(calc_dep.keys()): 
     v = calc_dep[k] 
     #print k, v 
     memo[k] = any(not memo[i] for i in v) 
    return memo[x] 

它首先计算集X号，输入， 依赖于取决于。然后它会计算这些数字，从底部开始并趋向x。

代码是如此之快，因为calc_dep的测试。它避免了计算多个依赖关系。因此，它可以在400毫秒内完成游戏（10000），而原始游戏则需要 - 我不知道多久。很长时间。

以下是性能测试：

Elapsed: 1000 0:00:00.029000 
Elapsed: 2000 0:00:00.044000 
Elapsed: 4000 0:00:00.086000 
Elapsed: 8000 0:00:00.197000 
Elapsed: 16000 0:00:00.461000 
Elapsed: 32000 0:00:00.969000 
Elapsed: 64000 0:00:01.774000 
Elapsed: 128000 0:00:03.708000 
Elapsed: 256000 0:00:07.951000 
Elapsed: 512000 0:00:19.148000 
Elapsed: 1024000 0:00:34.960000 
Elapsed: 2048000 0:01:17.960000 
Elapsed: 4096000 0:02:55.013000 

它相当活泼。