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>Following <a href="http://stackoverflow.com/users/6246044/rory-daulton">Rory Daulton</a>'s advice to use dynamic programming, I rewrote the <code>which_player_wins</code> method as follows:</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]

def which_player_wins(n):
    moves = [2, 3, 5]
    table = {j:"" for j in range(n+1)}
    table[0] = "Second"     # If it is the first player's turn an no stones are on the table, the second player wins
    table[1] = "Second"     # No legal moves are available with only one stone left on the board

    for i in range(2,n+1):
        next_n = [i - move for move in moves if i - move &gt;= 0]
        next_n_results = [table[k] for k in next_n]
        if any([result == "Second" for result in next_n_results]):
            table[i] = "First"
        else:
            table[i] = "Second"

    return table[n]

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

<p>This led to successfully solving the challenge (see below).</p>

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

python algorithm