如何使此方法非递归?

通常,只有当递归函数 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。

“疯狂”是指:

>>> 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)之前重复很长一段时间,所以你的记忆装饰器没有按它应该的方式工作。

通过从底部开始,可以确保每次递归调用都会立即命中结果字典。你可能会使用额外的空间,但不会重复太久。

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

嗯,递归主要是关于能够执行一些代码,而不会丢失以前的上下文及其顺序。特别是,函数帧在递归期间放置并保存到调用堆栈上,因此对递归深度进行了限制,因为堆栈大小是有限的。通过在堆内存上创建状态堆栈,可以手动管理/保存每次递归调用所需的信息,从而“增加”递归深度。通常,可用堆内存量大于堆栈内存量。思考:良好的快速排序实现通过创建一个具有不断变化的状态变量的外部循环(在qs示例中的上/下数组边界和pivot)来消除递归到更大的方面。

在我输入这个代码时,MartinV.Lwis给出了一个很好的答案,关于如何将递归函数转换为循环。

您可以稍微修改一下递归版本:

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三次。

我不确定这是否算作是您提出的原始算法的迭代版本,但这里是一个记忆迭代版本:

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

它相当迅速。