Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Why is Fibonacci misimplemented so often?
3 points by globalrev on Aug 12, 2008 | hide | past | favorite | 4 comments
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.)



I 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.


you'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)


Perhaps because in the original (Sanskrit) implementation, Fib(10) = 89?

http://en.wikipedia.org/wiki/Fibonacci_number


It's not only Fibonacci-- "off by one" errors are more common than you'd think.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: