How to speed up a recursive algorithm
<p>I'm trying to solve the Hackerrank challenge <a href="https://www.hackerrank.com/challenges/game-of-stones-1">Game of Stones</a>, a (shortened) problem statement of which is copied below.</p>

<p><a href="http://i.stack.imgur.com/Vqgl1.png"><img src="http://i.stack.imgur.com/Vqgl1.png" alt="enter image description here"></a></p>

<p>I came up with the following solution:</p>

<pre><code># The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

def which_player_wins(n):
    if n &lt;= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        next_ns = map(lambda x: n - x, legal_moves)
        next_ns = filter(lambda x: x &gt;= 0, next_ns)
        next_n_rewards = map(which_player_wins, next_ns)      # Reward for opponent
        if any(map(lambda x: x=="Second", next_n_rewards)):            # Opponent enters a losing position
            return "First"
        else:
            return "Second"

for n in ns:
    print which_player_wins(n)
</code></pre>

<p>The algorithm is essentially the minimax algorithm as it looks one move ahead and then recursively calls the same function. The problem is that in Hackerrank, it is terminating due to timeout:</p>

<p><a href="http://i.stack.imgur.com/7fynV.png"><img src="http://i.stack.imgur.com/7fynV.png" alt="enter image description here"></a></p>

<p>Indeed, I've noticed that evaluating <code>which_player_wins(40)</code> already takes ~2 seconds. Any ideas for a faster solution which would not time out?</p>

<p>Your solution would work (though very slowly) if you had infinite recursion levels available. But since you're not re-using already calculated results you are very quickly hitting Python's recursion limit.  One good solution, as suggested above, is to re-write the code using a non-recursive algorithm. </p>

<p>Alternatively, you could keep the code you have, but get it to re-use any result that you've already seen before. This is called memoization, and an easy way to implement that is to add a memoization decorator to the part of the code that computes the next move. Here's a way to use memoization to speed up your recursive algorithm, which I think is what you've specifically asked for:</p>

<ol>
<li><p>Convert all of the code after the first <code>else</code> into a function, <code>next_move(n)</code> that returns either 'First' or 'Second'.</p></li>
<li><p>Add a <code>memoize(f)</code> function which will take <code>next_move(n)</code> and avoid the recursion call if the result for n has already been calculated. </p></li>
<li><p>Add the decorator line <code>@memoize</code> immediately before the <code>next_move</code> definition.</p></li>
</ol>

<p>Resulting code:</p>

<pre><code>T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def next_move(n):
    next_ns = map(lambda x: n - x, legal_moves)
    next_ns = filter(lambda x: x &gt;= 0, next_ns)
    next_n_rewards = map(which_player_wins, next_ns)  # Reward for opponent
    if any(map(lambda x: x == "Second", next_n_rewards)):  # Opponent enters a losing position
        return "First"
    else:
        return "Second"

def which_player_wins(n):
    if n &lt;= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        return next_move(n)

for n in ns:
    print which_player_wins(n)
</code></pre>

<p>This hugely speeds up the calculation as well as reducing the levels of recursion required. On my computer n=100 is solved in 0.8 ms.</p>

python algorithm