Seven cool Fibonacci functions

Mikail Khan
Oct 24, 2020 · 3 min read
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.

def fib(n):
if (n < 2):
return 1
return fib(n - 1) + fib(n - 2)

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

fib 0 = 1
fib 1 = 1
fib n = (fib (n - 1)) + (fib (n - 2))selection-clipboard: primary

Traditional Iterative

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

def fib(n):
a, b = 1, 1
for i in range(n):
a, b = b, a + b
return b

Binet’s Formula

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

Credit: Art of Problem Solving

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

def fib(n): 
return int((((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n)/5**0.5)

Haskell zipWith

Here’s where the fun stuff starts:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

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:

[1, 1] -- starting list-- Add the offset list to the non offset list  [1, 1]
+ [1]
-- resulting in:
[1, 1, 2]
-- and then again;
[1, 1, 2]
+ [1, 2]
-- resulting in:
[1, 1, 2, 3]

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.

def fibs(n): [fib(x) for x in range(n) for fib in [lambda x: 1 if x < 2 else fib(n - 1) + fib(n - 2)]]

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:

fn fib(n: usize) -> usize {
(0..n).fold((0, 0), |(a, b), _| (b, a + b)).1
}

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.

def fibs():
a, b = 1, 1
while True:
yield b
a, b = b, a + b

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!

CodeX

Everything connected with Code & Tech!

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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