Seven cool fibonacci functions

Image for post
Image for post
Photo by Ludde Lorentz on Unsplash

Whenever I learn a new language, some of the first things I write are some simple Fibonacci sequence functions, one recursive, one iterative, and one to make a sequence of the fibonacci numbers up to n. These three problems usually reveal a good bit of the difference in philosophy between languages, or demonstrate some of the different ways to approach a problem within a language. Here are some of the coolest fibonacci functions I’ve found.

Traditional Recursive

Here’s the standard recursive Fibonacci function in Python. We’ve all seen it before; it’s pretty boring and incredibly slow.

It does look pretty elegant in Haskell with pattern matching though:

Traditional Iterative

The iterative version, of course, is incredibly fast in comparison. It’s still pretty boring though.

Binet’s Formula

Binet’s formula is a formula for the nth fibonacci sequence:

Binet’s formula
Binet’s formula
Credit: Art of Problem Solving

And this is the first one liner so far, but it’s pretty lame:

Haskell zipWith

Here’s where the fun stuff starts:

This creates a lazily generated infinite list of fibonacci numbers. Using it, we can access the nth fibonacci number by indexing or slicing the infinite list. For those unfamiliar with Haskell, this probably looks pretty magical, but I’ll try to explain it somewhat without trying to explain Haskell in general.

Essentially, for each element after the first two, we add the list to itself, but offset it by one:

Recursive Python Oneliner

This is a profoundly stupid implementation, but it’s what I came up with when asked to write a fibonacci sequence one liner in Python without using Binet’s formula.

Essentially, this function uses a one element list comprehension to create a fibonacci function inline. It’s slower than even the standard recursive function, but it’s a funny trick.

.fold() Oneliner

This next one is a pretty cool take on the standard iterative version which works in any language with a .fold() method and anonymous functions. Here’s what it looks like in Rust:

This is pretty straightforward to understand if you’re familiar with .fold() and higher level functions, and in Rust it’s just as fast as the standard iterative function.

Infinite Generator

Haskell’s zipWith fibonacci function is neat in part because it lazily generates an infinite list of fibonacci numbers which can later be indexed or sliced. While laziness is a core part of Haskell, this can also be done in languages with generators or lazy iterators.

Well, that’s the last one I’ve got, but I’m sure there’s plenty that I’ve missed. In particular, I’m interested in any neat Lisp solutions. If you’ve got anything cool, please feel free to share it below!

Written by

Math+CS Major at Purdue University, Hobbyist Gamedev

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store