Fibonacci in One Line Python

When I googled “Fibonacci Python” today, I found a lot of algorithms (most of them easy to understand). But I wondered — is there a Python one-liner to find Fibonacci numbers in the most concise way? As it turns out, there is! Read on to learn how to write the Fibonacci algorithm in one line of Python code.

The popular Italian mathematician Fibonacci (original name: “Leonardo of Pisa”) introduced in the year 1202 the Fibonacci numbers – with the surprising observation that these numbers occur everywhere in various fields such as math, art, and biology.

Definition

What are Fibonacci numbers? The Fibonacci numbers are the numbers of the Fibonacci series. The series starts with the numbers 0 and 1. Each following series element is the sum of the two previous series elements. That’s already the algorithm to calculate the Fibonacci series!

Code

We consider the following problem: Given a number n>2. Calculate a list of the first n Fibonacci numbers in a single line of code (starting from the first Fibonacci number 0)!

# Dependencies
from functools import reduce


# The Data
n = 10


# The One-Liner
fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (n-2), [0, 1])


# The Result
print(fibs)

Listing: Calculating the Fibonacci series in one line of Python code.

What’s the output of this code snippet?

How It Works

Let’s start with the reduce function — how does it work? We consider the reduce function with three parameters: reduce(function, iterable, initializer).

    “Apply function of two arguments cumulatively to the items of sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the sequence. If the optional initializer is present, it is placed before the items of the sequence in the calculation, and serves as a default when the sequence is empty. If initializer is not given and sequence contains only one item, the first item is returned.”

Documentation

The reduce function is useful if you want to aggregate state information that is just computed “on the fly”. For example, you compute the new Fibonacci number based on the previous two Fibonacci numbers that have just been computed. This is difficult to achieve with list comprehension (see Chapter 3) because you cannot (with standard means) access the newly created values from the list comprehension.

In the puzzle, we use the reduce function reduce(function, iterable, initializer). with the idea of consecutively adding the new Fibonacci number to an aggregator object that incorporates one value at a time from the iterable object as specified by the function. Here, we use a simple list as aggregator object with the two initial Fibonacci numbers [0, 1]. Recap that the aggregator object is handed as first argument to the function (in our example x). The second argument is the next element from the iterable. However, we initialized the iterable with (n-2) dummy values – simply to force the reduce function to execute function (n-2) times. Therefore, we use the throw-away parameter “_” to indicate that we are not really interested in it. Instead, we simply append the new Fibonacci number to the aggregator list x, calculated as the sum of the previous two Fibonacci numbers.

In summary, you’ve improved your understanding of another important pattern for Python one-liners: using the reduce function to create a list that dynamically uses the freshly updated or added list elements to compute new list elements. You will find this useful pattern quite often in practice.

Comments

  1. fib=lambda n:reduce(lambda x,y:(x[0]+x[1],x[0]),[(1,1)]*(n-2))[0]

  2. Hi Chris,
    nice article but the result is faulty.
    fib(10) is 55 and not 34 which is the last number in your printed fibs list.
    https://en.wikipedia.org/wiki/Fibonacci_number
    Better code:
    # The One-Liner
    fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (n-2), [1, 1])
    # The Result
    print(fibs[-1])

    1. Author

      Hey Thomas! 🙂
      I guess it depends — sometimes 0 is included into the Fibonacci sequence, sometimes not. Even the Wikipedia article you cite indicates that the sequence may start with 0… Anyway, great comment – thanks! 🙂

      1. Definitely it doesn´t depend. Even if you include fib(0) = 0 still fib(10) is 55 and not 34. The first 21 Fibonacci numbers F(n) for n = 0, 1, 2, …, 20 are:

        F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14
        0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
        F15 F16 F17 F18 F19 F20
        610 987 1597 2584 4181 6765

        1. Author

          If you consider 0 as the first Fibonacci number, 34 is the tenth Fibonacci number (e.g. https://www.mathsisfun.com/numbers/fibonacci-sequence.html). I would not consider the number 0 as the “zeroth” Fibonacci number (but the first one). Thus, fib(10) should be considered the “eleventh” Fibonacci number — much like the indexing l[10] returns the eleventh list element.

          Anyways, I’ve adapted the problem formulation to avoid further confusions: … (starting from the first Fibonacci number 0)

Leave a Comment