Python 再帰関数をわかりやすく解説（AIプログラミング 第５回）
はじめに
「ゲーム木」を扱う上で「再帰関数」はほぼ必須っぽかったので詳しく勉強していきます。
再帰関数とは
自分自身を呼び出す関数です。そもそも「再帰」という言葉で検索することは少ないと思います。「def関数内で自分自身の関数を使う」「def内でループしている」などで検索していて「再帰関数」という言葉が出てくることが多いと思います。
基本（前回のおさらい）
例：
def func(n): if n <= 0: return n return n + func(n-1) print(func(10))
実行してみると「55」（1から10までの和）が表示されました。
print(func(10))
func関数を「n=10」で呼び出しています。
return n + func(n-1)
func(10)で「10 + func(9)」を返します。
func(9)で「9 + func(8)」を返します。
func(8)で「8 + func(7)」を返します。
：
func(1)で「1 + func(0)」を返します。
func(0)で（if n <= 0:）「0」を返します。
一行にまとめます
func(10)で「10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0」を返します。
つまり、print(func(10))で「55」を表示することになります。
for文で書くとどうなるか
def func2(n): total = 0 for i in range(n, 0, -1): total += i return total print(func2(10))
あれ？そんなに変わらない？
for i in range(n, 0, -1):
これでは「0」を返していないので、厳密には「for i in range(n, -1, -1):」がいいかもしれないです。また「for i in range(n+1):」でも結果は同じですが、処理をする順番を考えると「10, 9, 8,・・, 2, 1, 0」が正解だと思います。
ここまではいろんなサイトで詳しく解説されています。問題はこの先です。
調べていても「再帰関数」の基本だけのところや基本の後に実践で使われたりしているので、いきなり実践だともう理解できなくなりました。
「基本ー応用ー実践」の「応用」の部分が大事だと思いますので、そのあたりを詳しく解説していきます。
応用（動きを追いかける）
例えば下記のプログラムでは「ｎ」と「ｉ」の値はどう変化するでしょうか。
def func3(n): if n >= 2: return for i in range(2): print("n=", n,"i=", i) # 再帰 func3(n+1) return func3(0)
とてもじゃないですが頭の中だけでは動きを追いきれないと思います。
実際に「print("n=", n,"i=", i)」で表示されるのはこうなります。
n= 0 i= 0 n= 1 i= 0 n= 1 i= 1 n= 0 i= 1 n= 1 i= 0 n= 1 i= 1
わかりやすく図にしてみます。
少しわかりにくいかもしれませんが、〇の中の数字が表示される順番です。
「n= 1 i= 0」と「n= 1 i= 1」は２回表示されています。
ここでピンときた方はすごいです。まだここでは気づきませんでした。
続けてこのプログラムではどうなるでしょうか。
def func3(n): if n >= 2: return for i in range(3): print("n=", n,"i=", i) # 再帰 func3(n+1) return func3(0)
結果はこう表示されます。
n= 0 i= 0 n= 1 i= 0 n= 1 i= 1 n= 1 i= 2 n= 0 i= 1 n= 1 i= 0 n= 1 i= 1 n= 1 i= 2 n= 0 i= 2 n= 1 i= 0 n= 1 i= 1 n= 1 i= 2
図にするとこうなります。
ここであることに気づきました。
下の図をご覧ください。
まさに「ゲーム木（木構造）」です。「ｎ」が選択回数（深さ）で「ｉ」が選択できる数です。つまり、三択を２回行っていることになります。
もう一つだけ例をあげます。
def func3(n): if n >= 3: return for i in range(2): print("n=", n,"i=", i) # 再帰 func3(n+1) return func3(0)
結果を図であらわすとこちらです。
２択「ｉ」を３回「ｎ」繰り返しています。頭の中だけでは動きは追えませんし、なぜこのような順番になるのかも今のところ理解できていません。
for文で書くとどうなるか
for i in range(2): print("n=", 0,"i=", i) for j in range(2): print("n=", 1,"j=", j) for k in range(2): print("n=", 2,"k=", k)
思ったよりシンプルです。これなら動きは追えそうです。
結果はこう表示されます。
n= 0 i= 0 n= 1 j= 0 n= 2 k= 0 n= 2 k= 1 n= 1 j= 1 n= 2 k= 0 n= 2 k= 1 n= 0 i= 1 n= 1 j= 0 n= 2 k= 0 n= 2 k= 1 n= 1 j= 1 n= 2 k= 0 n= 2 k= 1
（すべてのfor文で「ｉ」を使っても大丈夫でしたが）for文を「ｉ」「ｊ」「ｋ」で区別することで「ゲーム木（木構造）」にした時のどの位置（深さ）なのかがわかりやすくなりました。
これで「ゲーム木」を扱う上で「再帰関数」はほぼ必須な理由がわかりました。
あとは「三目並べ」でなら、その局面で勝負が付いたら点数をつけ、勝負がまだ付いてなければ次の手を考えることで「再帰関数」を使えそうです。
