5 ms·
Ok, I'll bite. - Recursion allows you to show correctness both in programming and mathematics. - plenty of compilers will reuse the current stack frame in
by toolslive 2y ago
Ok, I'll bite.
- Recursion allows you to show correctness both in programming and mathematics.
- plenty of compilers will reuse the current stack frame in a tail call.
- samatman 2y agoCounterpoint: https://news.ycombinator.com/item?id=41974171 https://news.ycombinator.com/item?id=41974171
- PaulHoule 2y agoTail call recursion doesn't turn the O(N^2) version of Fibonacci into O(N) but at least memoization turns it to O(N log N) or something. It's true that recursive algorithms can be easy to analyze. If you really knew your math you could do Fibonacci as O(1).
- xyzzyz 2y agoYou cannot do Fibonacci in O(1). You can reasonably do it in O(log n), though. Recursive Fibonacci is not O(n^2) either, it’s exponential.
- deleted 2y ago[deleted]
- tomsmeding 2y agoIf you have O(1) arbitrary-precision floating-point operations in O(1), you can do Fibonacci in O(1) by Binet's formula. But you don't, so you can't. Also, by a similar argument, the O(log n) by matrix exponentiation is really O(n log(n)^2 log(log(n))) by Schönhage-Strassen, I think. (The sequence is exponential in n, so the number of digits is O(n).) I may have miscounted the logs.
- xyzzyz 2y agoYou’re exactly right, I omitted the Schonhage Strassen just to simplify the point.
- WolfeReader 2y agohttps://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-form_expression https://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-fo... If exponentiation is done using floating-point arithmetic, this is O(1)
- xigoi 2y agoFloats only have a finite precision.
- chowells 2y agoIf you're fine getting wrong answers after the first 73, sure. Some people have higher standards than that.
- xyzzyz 2y agoExponentiation is not a constant time operation, and floating points have finite precision.
- WolfeReader 2y agoExponentiation is constant-time on floats. But as noted by sibling comments, the precision is a problem.
- xyzzyz 2y agoEverything is constant time is your precision is limited. Even the naive, recursive algorithm on integers is constant time if your integer size is limited (it will just be an exponentially big constant). To be able to meaningfully talk about complexity, you need to assume that something is not limited, and once you do that for floats, you’ll find that their exponentiation is no longer constant time.
- bodhiandphysics 2y agono... you can do fibonacci as O(log n)... you cannot represent (1 + sqrt(5))/2 on a computer.
- Smaug123 2y agoYou literally just did! The problem is not representing the number, it's computing digits.
- xyzzyz 2y agoYou totally can. Here is a O(log n) implementation of the Binet formula with infinite precision: https://github.com/xyzzyz/FibBinet/blob/master/FibBinet.hs https://github.com/xyzzyz/FibBinet/blob/master/FibBinet.hs
- norir 2y agoThere is a simple tail recursive implementation of fibonacci that is O(N) and doesn't use memoization. I'll leave it as an exercise for the reader.
- atn34 2y agoThe natural recursive implementation is exponential, and the memoized version is O(n)