Fibonacci, Leonardo da Pisa (Wikipedia) |

**Preamble**

The Fibonacci sequence $F_{n} = F_{n-1} + F_{n-2}$ is famous for both artistic and pure mathematical curiosity as an integer sequence. A simple implementation of this sequence appears as a standard programmer's entry-level job question, along with finding factorial and greatest common divisor. In this short post, we will show how to implement $F_{n}$ with recursion in Python one-liner.

**Fibonacci Recursion in Python**

**Here is a one-liner**

f = lambda n : n if n < 2 else f(n-1)+f(n-2) ; [f(n) for n in range(0,13)]

Let's dissect the one line. $f$ is our function that computes the $nth$ member of the sequence in a recursive fashion.

For example, a recursion of $f$ at $n=3$ follows the following depth as recursive calls:

- Upper level, n=3 : f(2)+f(1)
- n=2 : f(1) + f(0)
- Returns 1+0 = 1
- n=1 : f(1)
- Returns 1
- Returns 2

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

**Computational efficiency**

To compute the sequence for a very large set, this implementation is obviously very slow. One would need to introduce caching within the recursion to avoid repeated computation.

**Reading list for novice coders**

- List comprehension originating from set builder notation.
- Lambda expressions so-called anonymous functions.
- Recursion, it is a beautiful concept in computer science.
- Range function in Python.

**Conclusion**

One of the most interesting programming tasks usually comes in implementing integer sequences. Note that Fibonacci day is celebrated on 23rd of November, the day this post is published.

**Postscripts**:- The complexity of 1 liner code above is $O(2^N)$, with caching it can be $O(N)$. Thanks to Tim Scarfe for pointing out Big-O complexities.