竹内関数

LISPハッカーである竹内郁雄先生が考案された不思議な関数です。定義は以下のとおりです。

この関数は自分自身を呼びだす再帰関数で、それが二重になっているという、とんでもないしろものです。どうとんでもないかというと、tarai (x, y, z) の結果は、x、y、z のどれかですが、たとえば、tarai(4,2,0) を計算するのに（結果は 4）、54回も tarai を呼ばなくてはなりません。これが、tarai(10,5,0) を計算するとなると343073回も呼び出すはめになります。

実は、tarai (x,y,z)は、まず、x と y を比較して x ≤ y なら y、そうでないときは、y と z を比較して y ≤ z なら z そうでないなら、x が答えになっています。つまり 3 つの値を比べて、そのなかから 1 つを選んでも同じ結果になるということです。これなら、人間がやっても、あっというまに答えがでます。なのにこんなに手間をかけてどうするんでしょうか。

この関数の正式名称「たらいまわし関数」といいます。この関数は結果に重要な意味があるわけではなく、計算するのに関数呼出をひたすら繰り返すことに意味があります。つまり、計算機の性能を測って比較するためのベンチマークテストに使います。

tarai (2n, n, 0) の計算では nⁿ に比例した回数 tarai が呼ばれます。どういうことかというと、tarai (20, 10, 0) で tarai が呼ばれ回数は tarai (4,2,0) で tarai が呼ばれる回数の 25 億倍ということになります。

これほど単純な定義で、引数の3つの値も結果の値も爆発することもなく、とてつもない回数の呼出を必要とする関数は他は例がありません。すごい関数です。

この関数は3つの値をとりますが、これに音を割り当てると、なんと、バッハ風？の音楽を奏でられることが知られています。面白いですね。この話はまたの機会に。

———————————————————————————————————————————

＊チバテレの情報番組「モーニングこんぱす」内で、総合文化学科が紹介されました。
”楽しい学生生活”の様子がよくわかります！
YouTubeの聖徳大学チャンネルをぜひご覧ください♪

※　ツイッター・インスタグラムも日々更新しています！