# Thursday Code Puzzler: Fibonacci Sequences

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

*Note: Even
though there really is nothing stopping you from finding a solution to
this on the internet, try to keep honest, and come up with your own
answer. It's all about the participation!*

**Generate the nth Fibonacci Number**

Today we'll tackle another classic CS problem, the Fibonacci sequence. The first two numbers in the sequence are 0 and 1, and each subsequent number is the sum of the previous two. So, it looks like

0,1,1,2,3,5,8,13,21 ......

What you have to do is provide a function that takes a parameter n that returns the Fibonacci number at the nth position.

Catch up on all our previous puzzlers here

## Comments

## Vijay Nathani replied on Thu, 2012/07/26 - 1:49am

Groovy solution. As a sample, first 8 numbers are printed.

## Straub Edwin replied on Thu, 2012/07/26 - 4:52am

## Tomas M. replied on Thu, 2012/07/26 - 6:45am

## Tomas M. replied on Thu, 2012/07/26 - 7:02am

Lets remember that in the real world sequence start from 1 to n (not like in developers world where collection starts from 0)

## Earnest Dyke replied on Thu, 2012/07/26 - 8:58am

Non-recursive version.

Corrected for correct Fibonacci sequence. E!

## Jake Rathman replied on Fri, 2012/07/27 - 8:31am

## Earnest Dyke replied on Thu, 2012/07/26 - 9:02am

Very big difference in performance between the recursive and non-recursive Java versions.

Earnie!

## Rodrigo Garcia replied on Thu, 2012/07/26 - 11:23am

I havent programmed in Java for a while, but I guess it could something like this:

int fibo(int n)

{

if(--n < 2) return n;

return fibo(n-1) + fibo(n-2);

}

## Vijay Nathani replied on Thu, 2012/07/26 - 12:21pm in response to: Vijay Nathani

Groovy Code for corrected Fibonacci sequence:

## Eric Jablow replied on Thu, 2012/07/26 - 2:11pm

The problem with code like:

is that you will in the midst of computing fib(20), you will call fib(10) a total of fib(20 - 10) times. Consider instrumenting the code:

After you call fib(20), counter will equal fib(20) too.The function fib is a pure function of its argument; you should only be calling fib(10) once if possible. You can cache your results, you can call results in separate threads and halt calls when another thread succeds in computing the value, or you can use generators as in the Groovy code given. Or, you can use formulas to divide and conquer:

So, computing fib(15) leads to fib(7) and fib(8), etc.

## Marek Dec replied on Fri, 2012/07/27 - 2:02am

As Eric says, this can be done much faster using a proper algorithm. I guess the syntaxis does not really matter here. What's important is that the n-th element can be calculated in O(log n) time using a divide and conquer algorithm.

I ran through a cool and understandable solution some time ago. It was based on the fact that following equality is true.

So the only thing to do is to raise the matrix to a power of n in logarithmic time (and I guess this is pretty straighforward).

I blogged a bit on that and posted some code on the internets: http://marekdec.wordpress.com/2012/07/26/some-fibonacci/

## Yaroslav Borovikov replied on Fri, 2012/07/27 - 1:08am

## ebenezer raj replied on Sat, 2012/07/28 - 9:48pm

using q

{last {x,sum -2#x}/[x-2;til 2]}10

to get the 10th sum = 34

## Andre Onuki replied on Wed, 2012/08/01 - 7:26am

## Joe Colburn replied on Thu, 2012/09/13 - 10:30pm

Returns 13:

## Marco González replied on Thu, 2012/12/20 - 5:48pm

This is a O(1) implementation.

To reach to this formula, a lot of mathematical work is needed, involving linear transformations, diagonalization (eigenvalues and eigenvectors), and lots of matrix properties.

But the result is worth!, it doesn't even seem to evaluate the Fibonacci number.