竹内関数
竹内関数（たけうちかんすう）は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。
概要
再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。
{\rm Tarai}(x, y, z) = \begin{cases}
  y & \mbox{ if }x \le y\\
  {\rm Tarai}({\rm Tarai}(x - 1, y, z), {\rm Tarai}(y - 1, z, x), {\rm Tarai}(z - 1, x, y)) & \mbox{ otherwise. }\\
\end{cases}
定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数、たらい関数 (Tarai function) とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。電電公社研究員（当時）の竹内郁雄が、1974年の夏前の頃、このような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである。竹内関数と命名したのは野崎昭弘である。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。
他のよくベンチマークに使われる関数と比較して、たとえばフィボナッチ数を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない（ワード長の整数演算さえ実装していれば十分）、再帰がたいして深くならない（たいした量のスタックを使えなくても十分）、といった特性があり、関数呼び出し（と戻り）のオーバーヘッドがものをいう、というベンチマークである。
マッカーシー版
ジョン・マッカーシーは竹内関数を記憶違いで z を返すように変更し、これがTak関数として広まった。以下がその定義である。
{\rm Tak}(x, y, z) = \begin{cases}
  z & \mbox{ if }x \le y\\
  {\rm Tak}({\rm Tak}(x - 1, y, z), {\rm Tak}(y - 1, z, x), {\rm Tak}(z - 1, x, y)) & \mbox{ otherwise. }\\
\end{cases}
計算量はずっと少ない（たとえば tarai(12, 6, 0) では 12,604,860 回 tarai が呼ばれるのに対し、 tak(12, 6, 0) では tak は 63,608 回しか呼ばれない）。
本質
竹内関数の出力は以下のものと同等である。
{\rm T0}(x, y, z) = \begin{cases}
  y & \mbox{ if }x \le y\\
  z & \mbox{ if }x > y \mbox { and } y \le z\\
  x & \mbox{ otherwise. }\\
\end{cases}
ドナルド・クヌースによる研究が、Textbook Examples of Recursion(1990)にある。
感覚化
数値データ等を視覚や聴覚でとらえられるようにすることがあるが（視覚の場合可視化という）、竹内関数の引数の値に音階を割り振り、3個の引数で和音のような音にした試みがある。