7 ms·
Why would anyone use recursion to calculate Fibonacci numbers other than as a microbenchmark for function call performance?
by fanf2 6y ago
Why would anyone use recursion to calculate Fibonacci numbers other than as a microbenchmark for function call performance?
- bbarn 6y agoIt's a great showcase of how a flashy looking solution is the wrong approach. A good candidate will know it can be written in 2 lines recursively, but that the stack will explode with a fairly low term number, and that iterating with a for loop is more efficient.
- eru 6y agoIn eg Python you can just add a memoization decoration, and get a linear solution from the naive recursive one. That's pretty neat.
- dotancohen 6y agoIn almost any language, a hashtable check after the base case check could be used in a similar manner.
- eru 6y agoYes. I just singled out Python, because the language is well-known, and adding the memoization is particularly straight-forward.
- dotancohen 6y ago> iterating with a for loop I'm struggling to understand what you mean? This is a learning opportunity for me, if you wouldn't mind posting a code sample or elaborating further.
- ajuc 6y agoSomething like this (might be subtly wrong, I wrote it in 2 minutes). int fib(int n) { if (n<=2) return 1; int fibNMinus2= 1; int fibNMinus1 = 1; int tmp; for (int i=3; i<=n; i++) { tmp = fibNMinus2+ fibNMinus1 ; fibNMinus2 = fibNMinus1; fibNMinus1 = tmp; } return fibNMinus1; } vs recursive solution which is pretty but slow (and will fail when you run out of stack) int fib(int n) { if (i<=2) return 1; return fib(n-1)+fib(n-2); }
- eru 6y agoOf course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop: def fib(n): if n =< 0: return (0, 1) else: a, b = f(n-1) return (b, a + b) (I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined exception. A better language than Python can run this recursive version for arbitrarily big numbers.)
- ajuc 6y agoIn practice iteration will be faster, even in Python (because there's less overhead). But yes, I should have written "naive recursive solution". There are many ways to fix it. It just wasn't what the question was about.
- eru 6y agoIn Python, yes. If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) But, agreed with everything else you wrote!
- 6y ago
- ForHackernews 6y agoFibonacci has a closed-form solution! Forget writing loops, you can write one damn equation. Runs in constant time.
- WJW 6y agoThe closed form solution is technically O(phi^N), so still exponential. It comes mostly from exponentiation not being constant time, see https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence https://stackoverflow.com/questions/360748/computational-com.... It'll only be constant time if your values fit into a hardware register and you can leverage the exponentiation instructions of your CPU. There is a O(log(N)) solution involving matrix exponentiation though, if you really need to get the big numbers.
- Taek 6y agoTechnically, Fib(n) at unbounded sizes is at least linear to compute. This is because the output of Fib(n) has O(n) bits in it. So even if the computation is free, it's still O(n) just to print the result. That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.
- Thrymr 6y agoOr in this case, just compute it from the closed form expression with no loop at all.
- eru 6y agoBecause it's the most straightforward implementation in many languages? (And you can also use recursion in the fastest implementations. You just wouldn't use the naive recursive solution.)
- ajuc 6y agoFastest implementation is one non-recursive equation (which I had to look up) :) fib(n) = (((1 + sqrt(5)) / 2)^n - ((1 - sqrt(5)) / 2)^n) / sqrt(5) I even understood, once, how to arrive at the magic numbers :)
- ForHackernews 6y agoDerivation is here http://mathonline.wikidot.com/a-closed-form-of-the-fibonacci-sequence http://mathonline.wikidot.com/a-closed-form-of-the-fibonacci...
- ajuc 6y agoWe've learnt on "discrete math" course at university how to derive closed form solutions to any similar recursive sequences using algebra and eigenvectors. I remember that it's possible but I forgot all the required math :) Now that I googled it it's not THAT bad https://medium.com/@andrew.chamberlain/the-linear-algebra-view-of-the-fibonacci-sequence-4e81f78935a3 https://medium.com/@andrew.chamberlain/the-linear-algebra-vi... Of course the only use is to look smart once a decade when the subject comes up :)
- enriquto 6y agoWhile your formula is correct, it is not an actual implementation. How many digits of the square root do you need to compute exactly for being sure that the value of the power does not change? Whether this is "fast" or not depends a lot on the concrete implementation of your arbitrary-precision real numbers. As a nice thing, the second term (after the first minus sign) is smaller than 1, so you can omit it by rounding the result to the nearest integer; all the game happens in the first term.
- 6y ago
- Smaug123 6y agoI, for one, prefer recursion to explicit iteration in most cases. Anyway, if you were going to write the answer in Haskell, it's a three-liner and it's recursive.
- Taek 6y agoFor Fibonacci, recursion is not the best or most efficient way to approach the problem, but I like using it as a recursion problem (artificially constrain the candidate to using recursion) because Fibonacci is so simple that you get to spend most of your time talking about recursion itself rather than talking about Fibonacci as a problem. At least for this part of the interview, I'm not worried about your problem solving skills I'm worried about your programming fundamentals. We'll test problem solving in a different session.