17 lines
693 B
Plaintext
17 lines
693 B
Plaintext
Fibonacci: three things that go wrong
|
|
=====================================
|
|
|
|
1) HashMap.computeIfAbsent as the memo, recursive mapping function, n = 10
|
|
-> java.util.ConcurrentModificationException
|
|
same idea written as get / compute / put -> 55
|
|
|
|
2) The answer outgrows a long
|
|
fib(92) = 7540113804746346429
|
|
fib(93) -> ArithmeticException: long overflow (Math.addExact refuses to wrap around)
|
|
plain + instead of addExact would silently return -6246583658587674878
|
|
|
|
3) Recursion depth, House Robber with every house worth 1, in a thread with a 256 KB stack
|
|
memo n = 500 -> 250
|
|
memo n = 50,000 -> java.lang.StackOverflowError
|
|
tabulation n = 50,000 -> 25000
|