竹内関数
定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数、たらい関数 (Tarai function) とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。電電公社研究員(当時)の竹内郁雄が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである。竹内関数と命名したのは野崎昭弘である。
特性として、他のよくベンチマークに使われる関数と比較して、たとえばフィボナッチ数を何の工夫もなく計算するいわゆるダム(dumb)フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない(ワード長の整数演算さえ実装していれば十分)、再帰がたいして深くならない(たいした量のスタックを使えなくても十分)、といったものがある。このためベンチマークとしては、その処理系の関数呼び出し(と戻り)のオーバーヘッドに集中して結果が出ること、メモリの少ないハードウェアや多倍長計算がまだ無い処理系などのような実験的な環境でも実装し測定できること、といった特徴がある。
一度計算した値を覚えておき、次の呼び出しではその値を使う。