このプログラムが終了することの証明

数学的帰納法 （の逆さま）になりますが、

• 円盤が１枚のときは終了することが自明
• 円盤がＮ枚のとき、Ｎが正の整数ならば、再帰呼び出しによってＮ−１の場合が２回呼び出される
• (...（（Ｎ−１）−１）... −１)を繰り返せば １になるので、これも終了する
• よって、このプログラムは終了する