Fonction de Takeuchi

La fonction de Takeuchi, abrégée tak ou parfois tarai, est la présentation récursive d'une fonction qui doit son nom à Ikuo Takeuchi (竹内郁雄). La présentation de la fonction, qui, par ailleurs, admet une définition non récursive assez simple, peut requérir des calculs très longs si le compilateur qui l'implante n'est pas performant. Pour cette raison, elle est souvent utilisée pour tester les performances de l'implantation des fonctions récursives par le compilateur d'un langage de programmation.

Définition

La définition de la fonction tak se fait de façon récursive :

$\tau (x,y,z)={\begin{cases}\tau (\tau (x-1,y,z),\tau (y-1,z,x),\tau (z-1,x,y))&{\text{si }}y<x\\y&{\text{autrement}}\end{cases}}$

Elle peut être définie plus simplement et surtout non récursivement :

$\tau (x,y,z)={\begin{cases}y&{\text{si }}x\leq y\\{\begin{cases}z&{\text{si }}y\leq z\\x&{\text{autrement}}\end{cases}}&{\text{si }}x>y\end{cases}}$

Les premières écritures de la fonction, maintenant désignée comme fonction tarai, étaient écrites en donnant z en retour à la place de y, mais sera changé dans les écrits ultérieurs.

Voir aussi

• Fonction 91 de McCarthy

Liens externes

• (en) Wolfram
• (en) TAK Function