subtract_a_square_lengths_recursive.py

from functools import lru_cache

@lru_cache
def a(n):
    import math
    def S(m):
        return [j * j for j in range(1, int(math.sqrt(m)) + 1)]
    if n == 0:
        return 0
    possible_moves = [n - s for s in S(n)]
    if any(a(n - s) % 2 == 0 for s in S(n)):
        return min(a(n - s) for s in S(n) if a(n - s) % 2 == 0) + 1
    else:
        return max(a(n - s) for s in S(n)) + 1

print([a(i) for i in range(20)])