Tak (functie) - Tak (function)
In de informatica is de Tak-functie een recursieve functie , genoemd naar Ikuo Takeuchi (竹 内 郁 雄). Het is als volgt gedefinieerd:
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
z
end
end
Deze functie wordt vaak gebruikt als benchmark voor talen met optimalisatie voor recursie .
tak () versus tarai ()
De oorspronkelijke definitie door Takeuchi was als volgt:
def tarai( x, y, z)
if y < x
tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y)
)
else
y # not z!
end
end
tarai is een afkorting voor た ら い 回 し tarai mawashi , "to pass around" in het Japans.
John McCarthy noemde deze functie tak () naar Takeuchi.
In bepaalde latere verwijzingen werd de y echter op de een of andere manier veranderd in de z. Dit is een klein, maar significant verschil omdat de originele versie aanzienlijk profiteert van luie evaluatie . Hoewel op precies dezelfde manier geschreven als andere, werkt de onderstaande Haskell- code veel sneller.
tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai(tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
Men kan deze functie gemakkelijk versnellen via memoisatie, maar luie evaluatie wint nog steeds.
De bekendste manier om tarai te optimaliseren, is door de wederzijds recursieve helperfunctie als volgt te gebruiken.
def laziest_tarai(x, y, zx, zy, zz)
unless y < x
y
else
laziest_tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(zx, zy, zz)-1, x, y)
end
end
def tarai(x, y, z)
unless y < x
y
else
laziest_tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
z-1, x, y)
end
end
Hier is een efficiënte implementatie van tarai () in C:
int tarai(int x, int y, int z)
{
while (x > y) {
int oldx = x, oldy = y;
x = tarai(x - 1, y, z);
y = tarai(y - 1, z, oldx);
if (x <= y) break;
z = tarai(z - 1, oldx, oldy);
}
return y;
}
Let op de extra controle voor (x <= y) voordat z (het derde argument) wordt geëvalueerd, waardoor onnodige recursieve evaluatie wordt vermeden.
