プログラマ脳を鍛える数学パズルQ08 優秀な掃除ロボット

#問題概要
前後左右に動く掃除ロボットが12ステップで移動できる経路のパターン数を求める。ただし同じ場所は2回通らないこととする。

#Code
深さ優先探索。再帰を使って書く。

N = 12 #動く回数

def dfs(path):
    if len(path) > N:
        return 1
    cnt = 0 #パターン数
    for d in [(0,1), (0,-1), (1,0), (-1,0)]:
        next = path[-1][0] + d[0], path[-1][1] + d[1]
        if next not in path:
            cnt += dfs(path + [next])
    return cnt

print(dfs([(0, 0)])) #初期位置を(0, 0)とする

#ToDo
Pythonの再帰は遅いらしい。スタックを使って書いたほうが早いか？