2010.Feb.26 | Add Comment

## Single-line Solution: Fibonacci number

As I mention in my previous post, next single-line function to implement is Fibonacci number.

By definition, the first two Fibonacci numbers are 0 and 1, and each remaining number is the sum of the previous two. Some sources omit the initial 0, instead beginning the sequence with two 1s. (by Wikipedia)

There are some variants to calculate Fibonacci number. First one is recursion:

Func<int, int> fib = null;

fib = n => (n < 2) ? 1 : fib(n-1) + fib(n-2);

As I show in the previous post, this code can’t be a solution (nonsingle-line code). By the way, this code is absolutely inefficient. It has order of **O(φ ^{n})** time complexity.

Next algorithm is computing Fibonacci number via its matrix representation. This algorithm is very efficient (order of **O(log _{2}n)** time complexity) but has great number of calculations (additions, multiplications, exponentiations). It will be difficult to understand such an implementation.

The best approach is the third variant. It is efficient enough **O(n)** and has just two operation. The algorithm can be written as

Fib2(n):

i := 1

j := 1

for k := 3 to n do

j := i+j

i := j-i

` return j`

This code can be implemented in C# 3.5, Linq as

int fib = Enumerable.Range(1, n).Skip(2).Aggregate(new KeyValuePair<int, int>(1, 1), (seq, index) => new KeyValuePair<int, int>(seq.Value, seq.Key + seq.Value)).Value;

Yes, it is quite long but it works!

I create a range from 1 to n; skip first two elements (we know they values); store initial values in the KeyValuePair instance (1 and 1). In the aggregator function I repeat calculations as in the loop above.

Can anyone implement the same functions using other programming languages and the single-line approach?

Great discussion of Fibonacci numbers calculation using various programming languages is here.

That is it!