long memotable[]; // filled with -1, with first elements 0 and 1
long fib(int n) {
if(memotable[n] != -1)
return memotable[n];
memotable[n] = fib(n-2) + fib(n-1);
return memotable[n];
}
Edit: Actually, the Haskell version can be O(1) in memory as the front of the list can be garbage collected, while the C++ version is O(n) in memory.
> Edit: Actually, the Haskell version can be O(1) in memory as the front of the list can be garbage collected, while the C++ version is O(n) in memory.
Do you expect the following code to run in constant space?
head (drop 1000000000 (let fibs = 0 : 1 : zipWith max fibs (tail fibs) in fibs))
Neither ghci nor ghc seems to run it in constant space.
That's because the entries in fibs are thunks which become very large. This runs in constant space:
zipWith' f (x:xs) (y:ys) = let r = f x y in r `seq` r : zipWith' f xs ys
head (drop (10 ^ 9) (let fibs = 0 : 1 : zipWith max fibs (tail fibs) in fibs))
