The non-recursive formula for Fibonacci numbers
(via the magic of power series and generating functions)
The Fibonacci numbers form one of the most famous integer sequences, known for their intimate connection to the golden ratio, sunflower spirals, mating habits of rabbits, and several other things.
By definition, the Fibonacci numbers are defined by a simple second-order recursion.
This is usually also the example illustrating that recursive functions are not always a good idea in computing.
For instance, consider the following function. (It is written in Python, but it is easy to translate to other programming languages.)
