In keeping with our recent theme of
generating famous number structures, we'll consider the Fibonacci sequence today. This post was also inspired by some of the examples
and exercises in the Structure and Interpretation of Computer
Programs (namely Exercise 1.13 and Exercise 1.19 for those that came for the
Scheme solutions.)
The story goes that the Fibonacci
numbers were so named by the Italian mathematician Leonardo Fibonacci
in the 1200's, when he discovered the sequence while forming a
mathematical model for rabbit populations. However evidence suggests
that the sequence was known to others before then (it seems to appear
in earlier Indian mathematics, for instance.)
The Fibonacci numbers also have an
interesting relationship with the Golden Ratio, namely that as we
take larger and larger numbers in the sequence, the ratio between one
number and the next approaches the Golden Ratio.
Or mathematically:
And these numbers pop up in all sorts
of places. Remember Pascal's triangle? Turns out if you draw some
“shallow diagonal” lines across the triangle and sum up the
numbers on each line, you get the Fibonacci sequence too!
(There's a nice picture of this here.)
Though that history is all well and
good, computation is always much more interesting! We'll look at four
different ways to generate the Fibonacci numbers, with Clojure taking
centre stage as our JVM language today, including some guest appearances from Python (or Jython if you like, so as to keep with the JVM theme.)
