Как сделать этот метод нерекурсивным?

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

Я думаю, понятно, как это работает. Я также понимаю, что для этой конкретной игры, возможно, есть более разумное решение, но мой вопрос общий. Однако это заставляет питона сходить с ума даже при относительно небольших затратах. Есть ли способ заставить этот код работать с циклом?

Спасибо

Вот что я имею в виду, переводя в цикл:

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

Как правило, рекурсивные функции можно преобразовывать в циклы, только когда они примитивно-рекурсивные ; это в основном означает, что они называют себя только один раз в теле. Ваша функция вызывает себя несколько раз. Такая функция действительно нуждается в стеке. Возможно сделать стек явным, например, со списками. Одна переформулировка вашего алгоритма с использованием явного стека:

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), поэтому ваш декоратор памятки не поможет так, как должен.

Начиная снизу, вы гарантируете, что каждый рекурсивный вызов немедленно попадает в словарь результатов. Возможно, вы используете дополнительное пространство, но далеко не возвращаетесь.

Вы можете превратить любую рекурсивную функцию в итеративную функцию, используя цикл и стек - по сути, выполняя стек вызовов вручную. См. этот вопрос или этот вопрос , например, для некоторого обсуждения. Здесь может быть более элегантное решение на основе циклов, но оно мне не бросается в глаза.

Answer 3

Вы можете немного изменить рекурсивную версию:

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. Затем он рассчитывает эти числа, начиная с нижней части и двигаясь в направлении х.

Код очень быстрый из-за теста для calc_dep. Это позволяет избежать расчета нескольких зависимостей. В результате он может выполнить Game (10000) менее чем за 400 миллисекунд, тогда как оригинал занимает - я не знаю, как долго. Долгое время.

Вот измерения производительности:

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

Это довольно быстро.

Answer 4

Ну, рекурсия в основном о возможности выполнения некоторого кода без потери предыдущего контекста и их порядка. В частности, функциональные фреймы помещаются и сохраняются в стек вызовов во время рекурсии, что дает ограничение на глубину рекурсии, поскольку размер стека ограничен. Вы можете «увеличить» глубину рекурсии, вручную управляя / сохраняя необходимую информацию для каждого рекурсивного вызова, создавая стек состояний в куче памяти. Обычно объем доступной памяти кучи больше, чем у стека. Подумайте: хорошие реализации быстрой сортировки устраняют рекурсию в большую сторону, создавая внешний цикл с постоянно изменяющимися переменными состояния (нижняя / верхняя границы массива и сводка в примере QS)

Пока я печатал, Мартин против Лёвиса опубликовал хороший ответ о преобразовании рекурсивных функций в циклы.