Number of Function Calls In Recursive Code
First, let me correct the program:

1 function win(n)
2     if memo(n) exists:
3         return memo(n)
4     if n ≤ 3:
5         memo(n) = true
6     else:
7         memo(n) = not win(n-2) or not win(n-3)
8     return memo(n)


Compared to your code, there are two main differences:


If the value of the function is already known, that it is immediately returned (lines 2&ndash;3).
Otherwise, we compute the value of the function recursively by invoking win rather than memo (line 7).


The running time of win depends on which values have already been calculated. For example, if you already computed the value of win on $n-2$ and $n-3$, then computing it on $n$ takes time $O(1)$. We can also bound the running time of win on input $n$ by $O(n)$, since lines 4&ndash;8 run at most once for every value of the input.

We could also implement win without any memoization:

1 function win(n)
2     if n ≤ 3:
3          return true
4     else:
5          return not win(n-2) or not win(n-3)


The running time of this implementation satisfies the recurrence
$$ T(n) = T(n-2) + T(n-3) + O(1), $$
with base case $T(n) = O(1)$ for $n \leq 3$. Using standard techniques, we determine that the running time is $\Theta(c^n)$, where $c \approx 1.3247$ is the unique real root of $c^3=c+1$.

Finally, let us take a look at some values of win:
$$
\begin{array}{c|cccccccccccccccc}
n &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 &amp; 15 &amp; 16 \\\hline
\mathit{win}(n) &amp; T &amp; T &amp; T &amp; T &amp; F &amp; F &amp; T &amp; T &amp; T &amp; F &amp; F &amp; T &amp; T &amp; T &amp; F &amp; F
\end{array}
$$
Notice the period of 5. We can easily prove the following formula by induction: for $n \neq 1$, $\mathit{win}(n)$ holds iff $n \bmod 5 \in \{0,1\}$. This gives an $O(1)$ algorithm for computing win.