#１．はじめに
再帰関数はプログラミングの最初の関門かもしれない。Pythonでハノイの塔を解きながら、再帰関数をマスターしよう。
再帰関数は、マトリョーシカのように、プログラムの構造が入れ子になっている。ぜひ、マトリョーシカをイメージしながら、以下の説明を読んでみてください。
#２．ハノイの塔
ハノイの塔は、以下を参照してください。ハノイの塔
簡単に説明すると、棒が３本あって、板を刺せるようになっている。左に板が何枚かある。板の大きさは下が一番大きくて、上に行くほど小さくなる。板を一枚ずつ動かして、最終的に全ての板を左から真ん中の棒に移したい。但し、小さい板の上に大きな板は置けない。
プログラミングの学習では、再帰関数を使って解く問題だ。
#３．考え方
１枚は超簡単。左から真ん中に移して、おしまい。
２枚の場合がポイント。いきなり、左の棒の小さい板を真ん中に移してはダメ。
（１）まず、小さい板は、一旦、の右のワーク用の棒に移す。
（２）それから、左に残った、大きい板を真ん中に移す。
（３）その後、小さい板を右から真ん中に移せば、OKだ。
つまり、n枚の板（この場合は２枚）、すべてを左から真ん中に移すためには、（１）一番下の一番大きい板を除くn-1枚（この場合は１枚）を、一旦、左から右のワーク用の棒に移す必要がある。
（２）そして、一番下の一番大きい板を左から真ん中に移した後で、（３）右のワーク用の棒にあるn-1枚の板（この場合は１枚）すべてを、真ん中に移せば、OKだ。
以下の説明では、上記の（１）から（３）を繰り返し説明する。以下の説明で出てくる（１）から（３）も上記の（１）から（３）と、基本的には、同じ意味になる。但し、「どこから、どこへ」は、「左、真ん中、右」の中で、場合によって変化する。
#４．再帰関数での解法
以下がハノイの塔の解法プログラムになる。後ほど実行するが、使う際には、板の枚数をNに代入する。
start=list(range(N,0,-1));end=[];tmp=[];i=0 #1
def print_hanoi(): #2
print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
if n<=0: return #4
hanoi(n-1,start,tmp,end) #5
end.append(start.pop()) #6
print_hanoi() #7
global i; i+=1 #8
print('上記は',i,'回目の操作後の状態') #9
hanoi(n-1,tmp,end,start) #10
print_hanoi() #11
print('上記は最初の状態') #12
hanoi(N,start,end,tmp) #13
簡単に解説する。数字はプログラムで#を付けた部分に該当する。
１．startは最初に左の棒に刺さっている板を表すリスト。初期状態は、下が一番大きく、１ずつ小さくなり、最後は１となるリスト。
endは最終的に板を移したい真ん中の棒に刺さっている板を表すリスト。最初は何も刺さっていないので、空（から）のリスト。
tmpは右のワーク用の棒に刺さっている板を表すリスト。こちらも最初は何も刺さっていないので空のリスト。
iは、何回目の操作かを表すために設定。
２．状態を表す。順番に「左、真ん中、右」の棒に刺さっている板を、リストで表す。
３．これがハノイの塔を解く関数。但し、再帰関数をとして使うので、マトリョーシカのように、入れ子になる。
引数に注意してもらいたい。最初のnが板の枚数。次がstartで、それを次のendに動かしたい。最後がtmp。
４．これがベースとなる終了条件。動かすべき板が０になれば、終了。
ベースとなる終了条件を忘れると、無限ループに陥るので、注意が必要だ。
５．３の関数を再帰的に使っている。但し、３の関数は第一引数のn枚すべてを、第二引数のstartから第三引数のendに移すように定義した。（第四引数はワーク用のtmpとした。）
ここでは、（１）一番下のnを除いた 残りのn-1枚すべて（第一引数）をstart（第二引数）から一旦、tmp（第三引数）に移す。（第四引数は残りの引数であるend。）
こうすることで、上からn-1枚はtmpに移るので、一番下にあるnを動かすことができるようになる。
６．５で上からn-1枚をtmpに移したので、左のstartの棒には、一番下のnだけが残っている。（２）その一番下の板を取り出してstart.pop()、真ん中のendの棒に移すend.append()（リストへの追加）。
７．ここで状態をプリント。
８．回数をカウントアップ。
９．分かりやすいように何回目の操作後かをプリント。
１０．６で一番大きい板は真ん中に移っている。（３）その一番大きい板の上に、右のワーク用の棒にあるn-1枚の板すべてを移す。引数に注目すると、やっていることが分かると思う。
１１．ここで最初の状態をプリント。
１２．分かりやすいようにコメントをプリント。
１３．実際の実行。Nは実際に使う際に、与える。
#５．実際にやってみよう
１．まずは板が１枚の場合。やるまでも無い気がするが何事も念入りに。Nはプログラムの冒頭で指定している。
N=1;start=list(range(N,0,-1));end=[];tmp=[];i=0 #1
def print_hanoi(): #2
print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
if n<=0: return #4
hanoi(n-1,start,tmp,end) #5
end.append(start.pop()) #6
print_hanoi() #7
global i; i+=1 #8
print('上記は',i,'回目の操作後の状態') #9
hanoi(n-1,tmp,end,start) #10
print_hanoi() #11
print('上記は最初の状態') #12
hanoi(N,start,end,tmp) #13
結果は以下の通り。左から真ん中に移して、おしまい。
ここでは、３の「考え方」で説明した（２）の部分だけが実行される。（１）に相当する#5や（２）に相当する#10を見てもらうと分かるけど、n-1が0になり、#4で何も実行されないことになる。
[1] [] []
上記は最初の状態
[] [1] []
上記は 1 回目の操作後の状態
２．次は、２枚のケース。１枚のケースと異なり、２枚のケース以降は右のワーク用の棒を使う。
N=2;start=list(range(N,0,-1));end=[];tmp=[];i=0 #1
def print_hanoi(): #2
print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
if n<=0: return #4
hanoi(n-1,start,tmp,end) #5
end.append(start.pop()) #6
print_hanoi() #7
global i; i+=1 #8
print('上記は',i,'回目の操作後の状態') #9
hanoi(n-1,tmp,end,start) #10
print_hanoi() #11
print('上記は最初の状態') #12
hanoi(N,start,end,tmp) #13
結果は以下の通り。数字は板の大きさを表す。リストの数字は、下にあるものから順番に出力するようにしている。つまり、リストの中の数字が降順に並んでいることがハノイの塔のルール上、必要となる。
２枚のケースでは、
（１）まず、小さい板を左から右のワーク用の棒に移す。（１回目の操作）
（２）そして、そうすることで、左の大きい板を真ん中に移すことが出来る。（２回目の操作）
（３）最後に、右の小さい板を真ん中の大きい板の上に移せば、OKだ。（３回目の操作）
[2, 1] [] []
上記は最初の状態
[2] [] [1]
上記は 1 回目の操作後の状態
[] [2] [1]
上記は 2 回目の操作後の状態
[] [2, 1] []
上記は 3 回目の操作後の状態
３．３枚以降はプログラムは省略。Nに代入する枚数を変えればOKだ。
結果は以下の通り。
[3, 2, 1] [] []
上記は最初の状態
[3, 2] [1] []
上記は 1 回目の操作後の状態
[3] [1] [2]
上記は 2 回目の操作後の状態
[3] [] [2, 1]
上記は 3 回目の操作後の状態
[] [3] [2, 1]
上記は 4 回目の操作後の状態
[1] [3] [2]
上記は 5 回目の操作後の状態
[1] [3, 2] []
上記は 6 回目の操作後の状態
[] [3, 2, 1] []
上記は 7 回目の操作後の状態
（１）**１回目から３回目までの操作で、２枚（つまり、n-1枚）を右のワーク用の棒に移している。この１回目から３回目の中に、２枚の場合の（１）から（３）が含まれる。**もちろん、「どこから、どこへ」の詳細は、ケースバイケース。
（２）そして、４回目の操作で、一番大きい３枚目（つまり、n枚目）を左から真ん中に移す。
（３）その後、**５回目から７回目までの操作で、右のワークにある２枚（つまり、n-1枚）を真ん中の一番大きい板の上に移して、おしまい。この５回目から７回目の中にも、２枚の場合の（１）から（３）が含まれる。**もちろん、「どこから、どこへ」の詳細は、ケースバイケース。
ここで気をつけてほしいのは、まず（１）で２枚を右のワーク用の棒に移す方法。２でやった２枚を左から真ん中に移すケースでは、右がワークになった。しかし、３枚の（１）で２枚を左から右に移すケースでは、当然のことながら、真ん中がワーク用になる。だから、１回目の操作で一番小さい板を、真ん中に移すことになる。
（３）で２枚を右から真ん中に移す場合も同様。ここでは左がワークになるので、５回目の操作では、一番小さい板を右から左に移している。
４．最後に４枚のケースをやって、おしまいにしよう。
[4, 3, 2, 1] [] []
上記は最初の状態
[4, 3, 2] [] [1]
上記は 1 回目の操作後の状態
[4, 3] [2] [1]
上記は 2 回目の操作後の状態
[4, 3] [2, 1] []
上記は 3 回目の操作後の状態
[4] [2, 1] [3]
上記は 4 回目の操作後の状態
[4, 1] [2] [3]
上記は 5 回目の操作後の状態
[4, 1] [] [3, 2]
上記は 6 回目の操作後の状態
[4] [] [3, 2, 1]
上記は 7 回目の操作後の状態
[] [4] [3, 2, 1]
上記は 8 回目の操作後の状態
[] [4, 1] [3, 2]
上記は 9 回目の操作後の状態
[2] [4, 1] [3]
上記は 10 回目の操作後の状態
[2, 1] [4] [3]
上記は 11 回目の操作後の状態
[2, 1] [4, 3] []
上記は 12 回目の操作後の状態
[2] [4, 3] [1]
上記は 13 回目の操作後の状態
[] [4, 3, 2] [1]
上記は 14 回目の操作後の状態
[] [4, 3, 2, 1] []
上記は 15 回目の操作後の状態
（１）１回目から７回目までの操作で、３枚（つまり、n-1枚）を右のワーク用の棒に移している。この１回目から７回目の中に、３枚の場合の（１）から（３）が含まれる。そして、３枚の場合の（１）の中に、２枚の場合の（１）から（３）が含まれ、３枚の場合の（３）の中にも、２枚の場合の（１）から（３）が含まれる。
（２）そして、８回目の操作で、一番大きい４枚目（つまり、n枚目）を左から真ん中に移す。
（３）その後、９回目から１５回目までの操作で、右のワークにある３枚（つまり、n-1枚）を真ん中の一番大きい板の上に移して、おしまい。この９回目から１５回目の中に、３枚の場合の（１）から（３）が含まれる。そして、３枚の場合の（１）の中に、２枚の場合の（１）から（３）が含まれ、３枚の場合の（３）の中にも、２枚の場合の（１）から（３）が含まれる。
今回も３枚のときと同様、ワーク用は変化する。
#６．まとめ
ハノイの塔におけるワーク用などの役割は、板の枚数などによって、変化する。
しかし、着目してほしいのは、５の２枚、３枚、４枚に記載した（１）（２）（３）の部分だ。
（１）まず、上からn-1枚を、左から右のワーク用に移し、
（２）そうすることで、一番下の大きい板を、左から真ん中に移すことが出来て、
（３）最終的に、上からn-1枚を、右のワークから真ん中に移せば、OKだ。
４のプログラムで言えば、（１）が５に、（２）が６に、（３）が１０に、対応する。この操作を、マトリョーシカよろしく、繰り返し、行っているのが、ハノイの塔の解法に使われている再帰関数ということになる。（なお、正確に言うと、純粋な再帰の部分は（１）と（３）です。）
#７．参考サイト
以下のサイトは、c++で記載されていますが、とても参考になるサイトです。著者の方は、僕が個人的に尊敬している方です。