## Saturday, September 4, 2010

### Fibonacci using SQL

An exercise of logic, thinking of solution on-the-fly:

```create or replace function generate_fib(_count int) returns table(n numeric)
as
\$\$

with recursive fib(cnt, a, b) as
(
select 1, 0::numeric, 1::numeric
union all
select cnt + 1, b, a + b from fib where cnt <= \$1 - 1
)
select a from fib;

\$\$ language 'sql';

select n from generate_fib(1000); -- will generate 1,000 fibonacci
```

It's been a while since I wrote my first fibonacci program in college, it's in Pascal and I wrote it in iterative fashion. What's more real world than applying it to database skills? :) Some SQL recursions are actually tail recursion under-the-hood, and as such, can be straightforwardly written in iterative manner. I believe Postgresql implements this kind of recursion(tail recursion) to an iterative one, that's why it doesn't have any limit(Sql Server recursive SQL limitations comes to mind) with the depth of its recursion. Having said that, here's the iterative version:

```public static void Main (string[] args)
{
for(int i  = 0; i < 10; ++i)
Console.WriteLine ("Hello World! {0} {1}",i, Fibonacci(i));
}

static int Fibonacci(int r)
{
int a = 0,  b = 1;

while(r-- > 0)
{
int n = a;
a += b;
b = n;
}
return a;
}
```

Output:
```Hello World! 0 0
Hello World! 1 1
Hello World! 2 1
Hello World! 3 2
Hello World! 4 3
Hello World! 5 5
Hello World! 6 8
Hello World! 7 13
Hello World! 8 21
Hello World! 9 34
```

And off the top of my head(from a very recent activity), here's the recursive version, sans googling:
```int Fib(int n)
{
if(n == 0 || n == 1)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
```