Does using functional languages help against computing values repeatedly?
Posted
by sharptooth
on Stack Overflow
See other posts from Stack Overflow
or by sharptooth
Published on 2010-04-23T05:30:40Z
Indexed on
2010/04/23
5:33 UTC
Read the original article
Hit count: 176
functional-programming
Consider a function f(x,y):
f(x,0) = x*x;
f(0,y) = y*(y + 1);
f(x,y) = f(x,y-1) + f(x-1,y);
If one tries to implement that recursively in some language like C++ he will encounter a problem.
Suppose the function is first called with x = x0
and y = y0
. Then for any pair (x,y) where 0 <= x < x0
and 0 <= y < y0
the intermediate values will be computed multiple times - recursive calls will form a huge tree in which multiple leaves will in fact contain the same pairs (x,y). For pairs (x,y) where x and y are both close to 0 values will be computed numerous times.
For instance, I tested a similar function implemented in C++ - for x=20
and y=20
its computation takes about 4 hours (yes, four Earth hours!).
Obviously the implementation can be rewritten in such way that repeated computation doesn't occur - either iteratively or with a cache table.
The question is: will functional languages perform any better and avoid repeated computations when implementing a function like above recursively?
© Stack Overflow or respective owner