Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
,
named after Ikuo Takeuchi (竹内郁雄). It is
defined as follows:
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
In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it...
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
.
tak vs. tarai
The original definition by Takeuchi was as follows:
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 short for tarai mawashi, "to pass around" in Japanese.
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
named this function tak after Takeuchi.
However, in certain later references, the y somehow got turned into the z.
This is a small, but significant difference because the original version benefits significantly by lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
.
Though written in exactly the same manner as others, the Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
code below runs much faster.
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)
You can easily accelerate this function via memoization
Memoization
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...
yet lazy evaluation still wins.
The best known way to optimize tarai is to use mutually recursive helper function as follows.
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
Here is an efficient implementation of 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;
}
Note the an additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
