Fonction de Takeuchi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques image illustrant l’informatique
Cet article est une ébauche concernant les mathématiques et l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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[modifier | modifier le code]

\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}

def tak( x, y, z)
  if y < x
    tak(
         tak(x-1, y, z),
         tak(y-1, z, x),
         tak(z-1, x, y)
       )
  else
    y
  end
end

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

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

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]