Posted by: Zeeshan Amjad | April 22, 2014

## Fibonacci Word

I came across an interesting concept Fibonacci word. It is formed by repeated concatenation of symbols, usually two alphabets, using the Fibonacci numbers way.

Here are the first few words

F0 = a

F1 = ab

F2 = aba

F3 = abaab

F4 = abaababa

F5 = abaababaabaab

Let’s do this coding but first make a integer version of the program.

Code Snippet
static int[] Fibonacci(int no)
{
var fib = new int[no];

fib[0] = 0;
fib[1] = 1;

for (var i = 2; i < no; i++)
{
fib[i] = fib[i – 1] + fib[i – 2];
}

return fib;
}

Now let’s make the string version of the program.

Code Snippet
static string[] FibonacciString(int no)
{
var fib = new string[no];

fib[0] = "a";
fib[1] = "b";

for (var i = 2; i < no; i++)
{
fib[i] = fib[i – 1] + fib[i – 2];
}

return fib;
}

The integer version and the string version of the programs are very similar to each other. Let’s try to make a generic  function. This is our first attempt.

Code Snippet
static T[] Fibonacci<T>(int no)
{
var fib = new T[no];

fib[0] = 0;
fib[1] = 1;

for (var i = 2; i < no; i++)
{
fib[i] = fib[i – 1] + fib[i – 2];
}

return fib;
}

This program has two problem. First the initialization of the first and second elements of Fibonacci word. It can be easily solved by passing the initial values as a parameter. Here is a modified version of the program.

Code Snippet
static T[] Fibonacci<T>(int no, T first, T second)
{
var fib = new T[no];

fib[0] = first;
fib[1] = second;

for (var i = 2; i < no; i++)
{
fib[i] = fib[i – 1] + fib[i – 2];
}

return fib;
}

But there is still another problem. There is still a compilation error.

Error    1    Operator ‘+’ cannot be applied to operands of type ‘T’ and ‘T’

We can solve this problem with the dynamic keyword of C#. We can convert the last and second last item of the Fibonacci word using dynamic keyword before applying the concatenation words.

Here is a modified version of Fibonacci word.

Code Snippet
static T[] FibonacciGeneric<T>(int no, T first, T second)
{
if (no < 2)
return null;

var fib = new T[no];

fib[0] = first;
fib[1] = second;

for (var i = 2; i < no; i++)
{
dynamic last = fib[i – 1];
dynamic secondlast = fib[i – 2];

fib[i] = last + secondlast;
}

return fib;
}