How do I make this method non-recursive?
Hey. This example is pretty specific, but I think it can apply to a wide range of functions. This is taken from some kind of online programming competition.
There is a game with a simple win condition. A draw is impossible. The game cannot go on forever, because every move brings you closer to the final condition. The function should, given the state, determine whether the player who should be moving now has a winning strategy. In this example, the state is an integer. The player chooses a non-zero digit and subtracts it from the number: the new state is a new integer. The winner is the player who reaches zero.
I have 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 there is probably a much smarter solution for this particular game, but my question is general. However, this makes python insane even for relatively small inputs. Is there a way to make this code work with a loop?
thank
This is what I mean by converting to 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
source to share
In general, you can only convert recursive functions to 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. You can make the stack explicit, for example. with lists. One reformulation of your algorithm using an explicit stack -
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 the stack frame; local variables here are x, str (x) and the loop iteration counter. Making the return values a bit tricky - I decided to set res to not-None if the function had just returned.
source to share
"Crazy" I assume you mean:
>>> Game(10000)
# stuff skipped
RuntimeError: maximum recursion depth exceeded in cmp
You can start at the bottom instead - a rough 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 are starting with a large number, you have a long way to go before you hit bottom (0) so that your reminder decorator doesn't help as it should.
Starting from the bottom, you ensure that every recursive call ends up in the results dictionary immediately. You are probably using extra space, but you are not giving away far.
You can turn any recursive function into an iterative function using a loop and a stack - essentially using the call stack manually. See this question or this question for example for a discussion. There might be a more elegant loop-based solution here, but it doesn't jump out at me.
source to share
Well, recursion is basically about being able to execute some code without losing previous contexts and their order. In particular, function frames are pushed and stored on the call stack during recursion, so restrictions are imposed on the recursion depth since the stack size is limited. You can "increase" the recursion depth by manually manipulating / storing the required information for each recursive call by creating a state stack in heap memory. Usually the amount of available heap memory is greater than the stack. Think about it: good quick sort implementations eliminate recursion for the bigger side by creating an outer loop with constantly changing state variables (bottom / top array bounds and pivot in the QS example).
While I was typing this, Martin v. Löwis posted a good answer about converting recursive functions to loops.
source to share
You can change 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 look at the numbers multiple times. For example, if you do 111, you don't need to look at 110 three times.
I'm not sure if this counts as an iterative version of the original algorithm you presented, but there is a memoized iterative version here:
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 computes the set of numbers on which the input signal x depends. It then calculates these numbers starting from the bottom and going in the x direction.
The code is so fast because of the calc_dep test. This avoids calculating multiple dependencies. As a result, it can play Game (10000) in less than 400 milliseconds, whereas the original takes - I don't know how long. For a long time.
Here are the 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.
source to share