python - 如何使此方法非递归？

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。