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)
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;

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;
        return Fib(n - 1) + Fib(n - 2);

If your language allows lazy-loading of list, use this:

Note: Actually, google-fu skills is more important at this age, but having an eidetic rote memory of simple code snippets such as this one sometimes help in some situations even though they are very few and far in between.

No comments:

Post a Comment