4 ms·
Something like this (might be subtly wrong, I wrote it in 2 minutes). int fib(int n) { if (n<=2) return 1; int fibNMinus2= 1;
by ajuc 6y ago
Something 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!
- ajuc 6y agoI can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. And I instinctively distrust Sufficiently Smart Compilers ;)
- eru 6y agoOh, your compiler doesn't have to be sufficiently smart. It merely has to avoid premature optimization: see this classic paper https://dspace.mit.edu/handle/1721.1/5753 https://dspace.mit.edu/handle/1721.1/5753 by Guy Steele. > I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. I guess that's the same overhead as in this imperative version: a, b = 0, 1 for _ in range(n): a, b = b, a + b
- tom_mellior 6y ago> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.
- eru 6y agoI just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.) GHC is sometimes able to do some of those transformations. > The recursive Python version above didn't use tail calls. Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
- tom_mellior 6y ago> Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls. I was talking about this code: def fib(n): if n =< 0: return (0, 1) else: a, b = f(n-1) return (b, a + b) Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.
- dotancohen 6y agoTrue, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer.
- eru 6y agoAgreed. I only left that out for brevity.
- crimsonaluca20 6y agoFor the code above memory complexity is still O(N) even in a language that optimizes for tail calls. This occurs because you have an additional expression that occurs AFTER your recursive call that means the system must hold everything on the call stack for it to work. Additionally you have a spelling error on line 5.
- suyjuris 6y ago> I say it works better, because it has the same asymptotic runtime [...] To be fair, while the asymptotic runtime may be the same, the C version is about 180 times faster.
- eru 6y agoYes. Though if we allow programs like the C example that give wrong answers or have undefined behaviour, I can write an even faster version that takes no time at all.
- throwawayiionqz 6y agoThe "better" recursive solution computes fib(n) and fib(n-1) at the same time. Linear time recursion! def f(n): if n<=2: return (1, 1) else: a, b = f(n-1) return (b, a+b) def fib(n): return f(n)[1]
- dotancohen 6y agoYou have a bug for the case of fib(0).
- throwawayiionqz 6y agoIndeed, if you wish the sequence to be defined at 0, eru's solution is better (and appeared earlier while I was typing)