Seven cool Fibonacci functions

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!