Config
Tested under clojure 1.10.3 and openjdk 17.0.1
Problem
Below is the slightly revised version of the memoized Fibonacci, and the general techniques refer to wiki memoization.
(def fib
(memoize #(condp = %
0 (bigdec 0)
1 1
(+ (fib (dec %)) (fib (- % 2))))))
(fib 225) ; line 7
I had thought that the above memoized Fibonacci in FP like Clojure would act in spirit as the equivalent to the imperative DP e.g. in Python below,
def fib(n):
dp = [0, 1] + [0] * n
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Question 1
Why did I actually get the following error when Fibonacci number was raised to 225 in my case?
Syntax error (StackOverflowError) compiling at 7:1
I also tried on the drop-in replacement memo on core.memoize and got the same error when Fibonacci number was raised to 110.
Tracing
Below I added tracing the recursive outlooks of the naive Fibonacci vs. the memoized Fibonacci,
(ns fib.core)
(defn naive-fib [n]
(condp = n
0 (bigdec 0)
1 1
(+ (naive-fib (dec n)) (naive-fib (- n 2)))))
(def memo-fib
(memoize #(condp = %
0 (bigdec 0)
1 1
(+ (memo-fib (dec %)) (memo-fib (- % 2))))))
(in-ns 'user)
(require '[clojure.tools.trace :refer [trace-ns]])
(trace-ns 'fib.core)
(fib.core/naive-fib 5)
(println)
(fib.core/memo-fib 5)
Overlapping sub-problems from the naive Fibonacci were clearly eliminated by the memoized Fibonacci. Nothing seemed suspicious to cause StackOverflowError at the first sight, the depth of the stack frames for the memoized Fibonacci was strictly linear to the input number n, and the width was limited to 1.
TRACE t427: (fib.core/naive-fib 5)
TRACE t428: | (fib.core/naive-fib 4)
TRACE t429: | | (fib.core/naive-fib 3)
TRACE t430: | | | (fib.core/naive-fib 2)
TRACE t431: | | | | (fib.core/naive-fib 1)
TRACE t431: | | | | => 1
TRACE t432: | | | | (fib.core/naive-fib 0)
TRACE t432: | | | | => 0M
TRACE t430: | | | => 1M
TRACE t433: | | | (fib.core/naive-fib 1)
TRACE t433: | | | => 1
TRACE t429: | | => 2M
TRACE t434: | | (fib.core/naive-fib 2)
TRACE t435: | | | (fib.core/naive-fib 1)
TRACE t435: | | | => 1
TRACE t436: | | | (fib.core/naive-fib 0)
TRACE t436: | | | => 0M
TRACE t434: | | => 1M
TRACE t428: | => 3M
TRACE t437: | (fib.core/naive-fib 3)
TRACE t438: | | (fib.core/naive-fib 2)
TRACE t439: | | | (fib.core/naive-fib 1)
TRACE t439: | | | => 1
TRACE t440: | | | (fib.core/naive-fib 0)
TRACE t440: | | | => 0M
TRACE t438: | | => 1M
TRACE t441: | | (fib.core/naive-fib 1)
TRACE t441: | | => 1
TRACE t437: | => 2M
TRACE t427: => 5M
TRACE t446: (fib.core/memo-fib 5)
TRACE t447: | (fib.core/memo-fib 4)
TRACE t448: | | (fib.core/memo-fib 3)
TRACE t449: | | | (fib.core/memo-fib 2)
TRACE t450: | | | | (fib.core/memo-fib 1)
TRACE t450: | | | | => 1
TRACE t451: | | | | (fib.core/memo-fib 0)
TRACE t451: | | | | => 0M
TRACE t449: | | | => 1M
TRACE t452: | | | (fib.core/memo-fib 1)
TRACE t452: | | | => 1
TRACE t448: | | => 2M
TRACE t453: | | (fib.core/memo-fib 2)
TRACE t453: | | => 1M
TRACE t447: | => 3M
TRACE t454: | (fib.core/memo-fib 3)
TRACE t454: | => 2M
TRACE t446: => 5M
Question 2
Why could Clojure assert at compile-time that the depth of merely 225 stack frames for the memoized Fibonacci in my case could potentially explode the whole JVM stack thus cease to run the recursion altogether? From the source code on memoize below, I could see that an empty hashmap was initiated to cache the arguments and the returns for the memoized Fibonacci. Did the said hashmap cause the assertion of StackOverflowError? Why?
(defn memoize
"Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use."
{:added "1.0"
:static true}
[f]
(let [mem (atom {})]
(fn [& args]
(if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)))))
Others - (for the sake of completeness but unrelated to the OP)
We can take advantage of loop recur to achieve something like TCO, or the laziness of iterate implementation.
(ns fib.core)
(defn tail-fib [n]
(loop [n n
x (bigdec 0)
y 1]
(condp = n
0 0
1 y
(recur (dec n) y (+ x y)))))
(defn lazy-fib [n]
(->> n
(nth (iterate (fn [[x y]]
[y (+ x y)])
[(bigdec 0) 1]))
first))
(in-ns 'user)
(require '[clojure.tools.trace :refer [trace-ns]])
(trace-ns 'fib.core)
(fib.core/tail-fib 2000)
(println)
(fib.core/lazy-fib 2000)
The tracing tells that they don't make any recursive call longer in effect.
TRACE t471: (fib.core/tail-fib 2000)
TRACE t471: => 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125M
TRACE t476: (fib.core/lazy-fib 2000)
TRACE t476: => 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125M
I've carefully investigated the problem and finally figured it out, hopefully.
At first, let's look at a comparable yet handy recursive implementation on memoized Fibonacci in Python, before we jump into study on it in Clojure.
def memo_fib(n):
def fib(n):
print(f"ALL: {n}")
if n not in dp:
print(f"NEW: {n}")
if n == 0:
dp[0] = 0
elif n == 1:
dp[1] = 1
else:
dp[n - 1], dp[n - 2] = fib(n - 1), fib(n - 2)
dp[n] = dp[n - 1] + dp[n - 2]
return dp[n]
dp = {}
return fib(n)
memo_fib(5)
We add two print clauses to trace the recursive executions on memoized Fibonacci. ALL denotes what actually enter the spawned call stacks even if they are already memoized, while NEW denotes what proportionally show up only if they have yet to memoize. Obviously, the total ALL steps are greater than the NEW ones, which is also evident on the output below,
ALL: 5
NEW: 5
ALL: 4
NEW: 4
ALL: 3
NEW: 3
ALL: 2
NEW: 2
ALL: 1
NEW: 1
ALL: 0
NEW: 0
ALL: 1
ALL: 2
ALL: 3
Let's also compare it to naive Fibonacci in Python below,
def naive_fib(n):
print(f"NAIVE: {n}")
if n == 0:
return 0
if n == 1:
return 1
return naive_fib(n - 1) + naive_fib(n - 2)
naive_fib(5)
We can see below that memoized Fibonacci does reduce the recursive steps thus improve the stack more efficiently over naive Fibonacci, which invalidates the explanation @Eugene Pakhomov posted:
Memoization does not affect the stack when the cache is empty.
NAIVE: 5
NAIVE: 4
NAIVE: 3
NAIVE: 2
NAIVE: 1
NAIVE: 0
NAIVE: 1
NAIVE: 2
NAIVE: 1
NAIVE: 0
NAIVE: 3
NAIVE: 2
NAIVE: 1
NAIVE: 0
NAIVE: 1
Back to memoized Fibonacci in Clojure, what we have been able to trace in the OP are just the NEW steps. To peek at the ALL steps, we have to trace memoize function itself inside out. Please help if you know how to do it conveniently.
Now it's time to conclude that memoize can help reduce repetitive recursive calls but it cannot entirely prevent recursive calls from spawning stack frames again and again for some of overlapping sub-problems. StackOverflowError emerges to surprise you if those sub-problems grow rapidly.