たらいまわし関数の恐怖

激指のY山さんのブログに激指の並列化の実験にtak関数を使った、との
記述があったので、なんだろう、と調べてみたら
なんと竹内先生が1976年に再帰のベンチマークとして考案された関数、とのことです。
こんなところで竹内先生の名前が出てきてびっくり。

で、関数はいたってシンプル。

int tarai(int x,int y, int z)
{
　　if ( x <= y ) return y;
　　return tarai( tarai(x-1,y,z), tarai(y-1,z,x), tarai(z-1,x,y) );
}


これだけです。
なんだこりゃ、という感じ。
再帰関数なのですが、それが引数の中に3つも入っている、という危険な構造です。

何をやってるか分からなかったのですが、ぐぐると
この関数に意味はないそうです（おいおい）。

次にちゃんとこれって終了するのかな？という疑問。
ということでトレースしてみます。

まず
tarai(0,0,0) を実行しますと・・・これは1回ですぐ終了します。
結果は0

では、
tarai(1,0,0) は・・・最初の条件には引っかからないので
　　tarai( tarai(x-1,y,z), tarai(y-1,z,x), tarai(z-1,x,y) );
の中の tarai(x-1,y,z) に tarai(0,0,0) が入って呼ばれます。
これは1回で終了。結果は0。
　　tarai(y-1,z,x) は tarai(-1,0,1) となって、
これも1回で終わって結果は0。
　　tarai(z-1,x,y) は tarai(-1,1,0) となって、
これも1回で終わって結果は1。

結局
tarai(0,0,1) となって自分自身が呼ばれます。
結果、1回で終わって結果は0

合計、5回呼ばれることになります。


では
tarai(10,0,0) だと・・・ 41回かかって結果は0

このあたりまではまだかわいいのですが、

tarai(10,5,0) 343073回かかって結果は10

といきなりめちゃくちゃな回数なってきます。
さらに、

tarai(15,10,0) 6540246905回かかって結果は15

軽くintの範囲を超えていきます。

ちゃんと収束するのが面白いです。

どういう振る舞いをするのかいまいち分かってないのですが
3のべき乗か階乗に比例して増えていく雰囲気です。

ちなみに竹内先生自身による解説が少しあります。
どう転んでもLisp（福音伝道者、あたりを参照のこと）
http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.files/frame.htm