3 ms·
Why is Fibonacci misimplemented so often?
Why is it that so many times, even among good programmers, the Fibonacci function is misimplemented?
Here it is from the OCaml tutorial:
<<#let rec fib n =
# if n < 2 then 1 else fib(n-1) + fib(n-2);;
val fib : int -> int = <fun>
#fib 10;;
- : int = 89
>>
Finonacci 0 is 0, not 1.
Thus: Fibonacci 10 is 55.
Corrected:
# let rec fibo n =
# if n < 2 then if n ==1 then 1 else 0 else fibo(n-1) + fibo(n-2);;
val fibo : int -> int = <fun>
# fibo 12;;
- : int = 144
# fibo 10;;
- : int = 55
#
(And yes it is a superslow exponential implementation but that is not the point here.)
- yan 18y agoI think that's the case because the Fibonacci sequence isn't interesting as a sequence itself to most developers, but as an example of basic recursion. And as an example of basic recursion, you can have a base case be slightly off without misrepresenting what the essence is.
- silverlake 18y agoyou're right, but you can implement the real fib by returning N instead of 1: let rec fib n = if n < 2 then n else fib(n-1) + fib(n-2)
- michael_dorfman 18y agoIt's not only Fibonacci-- "off by one" errors are more common than you'd think.
- MaysonL 18y agoPerhaps because in the original (Sanskrit) implementation, Fib(10) = 89? http://en.wikipedia.org/wiki/Fibonacci_number http://en.wikipedia.org/wiki/Fibonacci_number