Everyone having studied science has met
Fibonacci numbers somewhere or another in his curriculum.
And everyone having studied recursion in programming languages
has at one moment or another been taught how to "optimize"
an exponentially slow recursive implementation of the Fibonacci function
into a linearly slow iterative loop.
Except they were lied to.
For that loop they learnt as a model to emulate is far from "optimal".
There exists an algorithm that is (asymptotically) infinitely faster.
And to understand how this algorithm may be devised
allows us to explore a few ways that expressive languages like Lisp
can open your mind to horizons unconceivable
using such inexpressive and awkward languages
as are mainstream in the industry.
Have a look at
fibonacci.lisp
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
fare) wrote,
