如何将此方法改为非递归？

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

递归主要是指在执行一些代码时，能够保持之前的上下文和顺序不变。具体来说，在递归过程中，函数的状态会被放到一个叫做调用栈的地方，这样就会限制递归的深度，因为栈的大小是有限的。如果你想“增加”递归的深度，可以通过手动管理和保存每次递归调用所需的信息，来创建一个在堆内存中的状态栈。通常，堆内存的可用空间比栈要大。想想看：好的快速排序实现会通过创建一个外部循环，使用不断变化的状态变量（比如数组的上下边界和枢轴）来避免对较大部分的递归。

在我写这些的时候，Martin v. Löwis 也发了一个很好的回答，讲的是如何把递归函数转换成循环。

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），这样你的记忆化装饰器就没法发挥应有的作用。

从底部开始，你可以确保每次递归调用都能立即找到结果的字典。这样可能会用到额外的空间，但你不需要递归太多层。

你可以通过使用循环和栈，把任何递归函数转换成迭代函数 -- 实际上就是手动运行调用栈。想了解更多，可以看看这个问题或者这个问题，里面有一些讨论。这里可能有更优雅的基于循环的解决方案，但我现在想不起来。

Answer 3

一般来说，只有当递归函数是原始递归时，才能把它转换成循环；这基本上意味着它在函数体内只调用自己一次。而你的函数是多次调用自己的，这种情况下，函数确实需要一个栈。我们可以用列表来明确地表示这个栈。下面是你算法的一种用显式栈重写的方式：

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 设置为非空值。