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>It seems from the problem description that you are able to keep the intermediate and final results from each calculation to use in later calculations. If that is so, a recursive algorithm is not optimal. Instead, use a dynamic programming style.</p>

<p>In other words, keep a global array that stores the results from previous determinations of wins and losses. When you determine for a new value of <code>n</code>, rather than recursing all the way to the end, use the previous determinations.</p>

<p>For example, when you get to <code>n=10</code>, you see that the first player removing 3 stones leaves 7 stones, which you have already seen as a win for the second player. Therefore, 10 stones is a win for the first player.</p>

<p>I believe that your recursive algorithm would calculate all over again the result for <code>n=7</code> rather than using the previous work.</p>

python algorithm