How to make this method non-recursive?

Question

Hey. This example is pretty specific but I think it could apply to a broad range of functions. It's taken from some online programming contest.

There is a game with a simple winning condition. Draw is not possible. Game cannot go on forever because every move takes you closer to the terminating condition. The function should, given a state, determine if the player who is to move now has a winning strategy. In the example, the state is an integer. A player chooses a non-zero digit and subtracts it from the number: the new state is the new integer. The winner is the player who reaches zero.

I coded this:

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

I think it's clear how it works. I also realize that for this specific game there's probably a much smarter solution but my question is general. However this makes python go crazy even for relatively small inputs. Is there any way to make this code work with a loop?

Thanks

This is what I mean by translating into a loop:

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

By "go crazy" I assume you mean:

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

You could start at the bottom instead -- a crude change would be:

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

# Now this will work:
print Game(10000)

This is because, if you start with a high number, you have to recurse a long way before you reach the bottom (0), so your memoization decorator doesn't help the way it should.

By starting from the bottom, you ensure that every recursive call hits the dictionary of results immediately. You probably use extra space, but you don't recurse far.

You can turn any recursive function into an iterative function by using a loop and a stack -- essentially running the call stack by hand. See this question or this quesstion, for example, for some discussion. There may be a more elegant loop-based solution here, but it doesn't leap out to me.

Answer 2

In general, it is only possible to convert recursive functions into loops when they are primitive-recursive; this basically means that they call themselves only once in the body. Your function calls itself multiple times. Such a function really needs a stack. It is possible to make the stack explicit, e.g. with lists. One reformulation of your algorithm using an explicit stack is

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

Basically, you need to make each local variable an element of a stack frame; the local variables here are x, str(x), and the iteration counter of the loop. Doing return values is a bit tricky - I chose to set res to not-None if a function has just returned.

Answer 3

Well, recursion mostly is about being able to execute some code without losing previous contexts and their order. In particular, function frames put and saved onto call stack during recursion, therefore giving constraint on recursion depth because stack size is limited. You can 'increase' your recursion depth by manually managing/saving required information on each recursive call by creating a state stack on the heap memory. Usually, amount of available heap memory is larger than stack's one. Think: good quick sort implementations eliminate recursion to the larger side by creating an outer loop with ever-changing state variables (lower/upper array boundaries and pivot in QS example).

While I was typing this, Martin v. Löwis posted good answer about converting recursive functions into loops.

Answer 4

You could modify your recursive version a bit:

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)

This way, you don't examine digits multiple times. For example, if you are doing 111, you don't have to look at 110 three times.

I'm not sure if this counts as an iterative version of the original algorithm you presented, but here is a memoized iterative version:

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]

It first calculates the set of numbers that x, the input, depends on. Then it calculates those numbers, starting at the bottom and going towards x.

The code is so fast because of the test for calc_dep. It avoids calculating multiple dependencies. As a result, it can do Game(10000) in under 400 milliseconds whereas the original takes -- I don't know how long. A long time.

Here are performance measurements:

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

It's reasonably zippy.