Does using functional languages help against computing values repeatedly?
- by sharptooth
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?
