「竹内関数」の版間の差分

\end{cases}</math>
 
定義からわかるように処理を次々に[[たらい回し]]にしていくことから、'''たらいまわし関数'''<ref>{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | page=185 | isbn=4-87408-414-1}}</ref>、'''たらい関数''' (''Tarai function'') とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。[[日本電信電話公社|電電公社]]研究員(当時)の[[竹内郁雄]]が[[1976年]]に考案した。竹内関数と命名したのは[[野崎昭弘]]である。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。
 
他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム(dumb)フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない(ワード長の整数演算さえ実装していれば十分)、再帰がたいして深くならない(たいした量のスタックを使えなくても十分)、といった特性があり、関数呼び出し(と戻り)の[[オーバーヘッド]]がものをいう、というベンチマークである。