Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

There is a well known question here that asks for a short (least characters) fibonacci sequence generator.

I would like to know if someone can generate the first N elements only, of the fibonacci sequence, in very short space. I am trying to do it in python, but I'm interested in any short answer, in any language. Function F(N) generates the first N elements of the sequence, either returns them as the return of the function or prints them.

Interestingly it seems that the code-golf answers start with 1 1 2, instead of 0 1 1 2. Is that a convention in code-golf or programming-in-general? (Wikipedia says the fibonacci sequence starts with zero.).

Python Sample (First 5 Elements):

def f(i,j,n):
    if n>0:
        print i;
        f(j,i+j,n-1)
f(1,1,5)
share|improve this question
1  
I think this is too similar to the linked question. Most solutions there can easily be modified to handle the first-n case. –  hammar Jan 17 '12 at 20:52
    
In the case of Python, the interesting thing is that I need four lines of code, and two levels of indentation in my sample. I suspect there is a one liner in python, but I can't find it. –  Warren P Jan 17 '12 at 20:56
2  
Everywhere I've seen, the base cases are defined as F_0 = 0, F_1 = 1 or equivalently F_1 = 1, F_2 = 1. The difference is whether you want to start the sequence at index 0 (more common in programming) or 1 (more common in math). –  hammar Jan 17 '12 at 21:19
1  
And defining F_0 = 0, F_1 = 1 has a definite benefit in simplicity with the matrix representation [[1 1][1 0]]^n = [[F_{n+1} F_n][F_n F_{n-1}]]. –  Peter Taylor Jan 17 '12 at 23:36
1  
@Peter: Now that a good reason to prefer one to the other (I'd long preferred 0, 1 on esthetic grounds, but don't believe those to be pressing in and of themselves). –  dmckee Jan 18 '12 at 3:33

24 Answers 24

up vote 27 down vote accepted

C

Didn't bother counting, but here's a fun example:

f(n){return n<4?1:f(--n)+f(--n);}
main(a,b){for(scanf("%d",&b);a++<=b;printf("%d ",f(a)));}

Proof it works.


I'm quite proud of this: I got bored, so I rearranged my code (with a few small additions) to make it where each line represents a value in the Fibonacci sequence.

                         #                                // 1
                         f                                // 1
                         //                               // 2
                        (n)                               // 3
                       {/**/                              // 5
                      return n                            // 8
                    <2 ? 1:f(--n)                         // 13
                +f(--n); } main(a, b)                     // 21
          {a = 0, b = 0;scanf("%d",&b); for(              // 34
;a < b; a+=1) { int res = f(a); printf("%d ", res); } }   // 55

Proof it works.

share|improve this answer
    
Nice. 90 chars (without newline). Save 2 bytes: a++<=b-> a++-b and return--n<3?1:f(n)+f(n-1). Plus you can avoid scanf if you require n to be in argc. –  ugoren Jan 18 '12 at 8:35
5  
+1 for massive style. It's kind of a code-haiku. –  Warren P Jan 18 '12 at 17:54

GolfScript, 16 characters

~0 1@{.2$+}*;;]`

Example output:

$ ruby golfscript.rb ~/Code/golf/fib.gs <<< "12"
[0 1 1 2 3 5 8 13 21 34 55 89]
share|improve this answer

Here's a one-liner Python. It uses floating-point, so there may be some n for which it is no longer accurate.

F=lambda n:' '.join('%d'%(((1+5**.5)/2)**i/5**.5+.5)for i in range(n))

F(n) returns a string containing the first n Fibonacci numbers separated by spaces.

share|improve this answer
    
I was thinking of doing this, but thought it would be too long. I didn't think about using flooring. Very nice. –  Kris Harper Jan 18 '12 at 0:04
    
Ah, Binet's formula. I also used it & it's accurate, at least till the 59th fibonacci number if you count 0 as the first. After that the numbers become too big & it starts using exponents. –  elssar Jan 18 '12 at 7:38
    
70 chars, 1 line, to define function. + 4 +crlf to invoke. Pretty good! –  Warren P Jan 18 '12 at 17:53

Perl, 50 characters

sub f{($a,$b,$c)=@_;$c--&&say($a)&&f($b,$a+$b,$c)}
share|improve this answer

Scala 71:

def f(c:Int,a:Int=0,b:Int=1):Unit={println(a);if(c>0)f(c-1,b,a+b)};f(9)

prints

0
1
1
2
3
5
8
13
21
34
share|improve this answer
    
Cool. I haven't even played with Scala yet. I will try it tonight at home. –  Warren P Jan 18 '12 at 17:54

I can give you a two line Python solution. This will return them as a list.

f = lambda n: 1 if n < 2 else f(n-1) + f(n-2)
g = lambda m: map(f, range(0,m))

print g(5)

You could have it print them out by adding another map to make them strings and then adding a join, but that just seems unnecessary to me.

Unfortunately I don't know how to put a recursive lambda into map, so I'm stuck at two lines.

share|improve this answer
    
What's it return for g(100)? ;) –  GigaWatt Jan 17 '12 at 22:13
    
@GigaWatt Heh, OP never said it had to be reasonable. Is the asymptotic running time something like O(n(1.62)^n)? –  Kris Harper Jan 18 '12 at 0:11
    
Here's one way you can (kind of) do this. Note that f(n) with n<=0 returns integers, and n>0 returns lists, so.. maybe it isn't ideal: f = lambda n: map(f, (-x for x in range(0, n))) if n > 0 else -n if n > -2 else f(n+1) + f(n+2) –  Dillon Cower Jan 19 '12 at 2:48
    
By the way, you missed the first 0 in your answer. Changing f to return n if n < 2 is one workaround. :) –  Dillon Cower Jan 19 '12 at 2:51
    
@DC I like your solution. Pretty creative. Yeah, I made mine start with 1, 1 because that's how I always learned it. I figured changing it was easy enough. –  Kris Harper Jan 19 '12 at 12:07

Python (78 chars)

I used Binet's formula to calculate the fibonacci numbers -

[(1+sqrt(5))^n-(1-sqrt(5)^n]/[(2^n)sqrt(5)]

It's not as small some of the other answers here, but boy it's fast

n=input()
i=1
x=5**0.5
while i<=n:
    print ((1+x)**i-(1-x)**i)/((2**i)*x)
    i+=1
share|improve this answer
    
Python (12 chars): print"11235" :) –  Joel Cornett May 13 '12 at 16:53
    
You can shave 2 chars off by getting rid of the parentheses around 2**i. ** have higher precedence than * –  Joel Cornett May 13 '12 at 17:05

Scheme

This is optimized using tail-recursion:

(define (fib n)
  (let fib ([n n] [a 0] [b 1])
    (if (zero? n) (list a)
        (cons a (fib (- n 1) b (+ a b))))))
share|improve this answer

Haskell

fib n = take n f
f = 0:1:zipWith (+) f (tail f)

Proof that it works.

share|improve this answer
    
You can make it one function using where –  Łukasz Niemier May 2 '12 at 8:30

J, 25 characters

I realise that J solutions are probably not what you're after, but here's one anyway. :-)

0 1(],+/&(_2&{.))@[&0~2-~

Usage:

    0 1(],+/&(_2&{.))@[&0~2-~ 6
0 1 1 2 3 5
    0 1(],+/&(_2&{.))@[&0~2-~ 10
0 1 1 2 3 5 8 13 21 34

How it works:

Starting from the right (because J programs are read from right to left),

2-~ 6 The ~ operator reverses the argument to the verb so this is the same as 6-2

Ignoring the section in brackets for now, 0 1(...)@[&0~ xtakes the verb in the brackets and executes it x times using the list 0 1 as its input - ~ again reverses the arguments here, giving x (...)@[&0 ] 0 1, meaning I can keep the input at the end of the function.

Within the brackets is a fork ],+/&(_2&{.) which is made up of three verbs - ], , and +/&(_2&{.).

A fork takes three verbs a b c and uses them like this: (x a y) b (x c y) where x and y are the arguments to the fork. The , is the centre verb in this fork and joins the results of x ] y and x +/&(_2&{.) y together.

] returns the left argument unaltered so x ] y evaluates to x.

+/&(_2&{.) takes the last two items from the given list (_2&{.) - in this case 0 1 - and then adds them together +/ (the &s just act as glue).

Once the verb has operated once the result is fed back in for the next run, generating the sequence.

share|improve this answer

Powershell - 35 characters

Powershell accepts pipeline input, so I'm of the belief that the n | in n | <mycode> shouldn't be against my count, but instead is just a part of initiating a "function" in the language.

The first solution assumes we start at 0:

%{for($2=1;$_--){($2=($1+=$2)-$2)}}

The second solution assumes we can start at 1:

%{for($2=1;$_--){($1=($2+=$1)-$1)}}

Example invocation: 5 | %{for($2=1;$_--){($1=($2+=$1)-$1)}}

Yields:

1
1
2
3
5

Interestingly, attempts to avoid the overhead of the for() loop resulted in the same character count: %{$2=1;iex('($1=($2+=$1)-$1);'*$_)}.

share|improve this answer

TI-Basic, 43 characters

:1→Y:0→X
:For(N,1,N
:Disp X
:Y→Z
:X+Y→Y
:Z→X
:End

This code can be directly inserted into the main program, or made into a separate program that is referenced by the first.

share|improve this answer
    
This is the first TI-BASIC solution I've ever seen here that wasn't by me :) +1 –  Timtech Jan 10 at 0:06
    
Also, note for other people that newlines are not counted here because they can be removed. –  Timtech Jan 10 at 0:13

APL (33)

{⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}

Usage:

   {⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}7
0 1 1 2 3 5 8
share|improve this answer

Python, 43 chars

Here are three fundamentally different one-liners that don't use Binet's formula.

f=lambda n:reduce(lambda(r,a,b),c:(r+[b],a+b,a),'.'*n,([],1,0))[0]
f=lambda n:map(lambda x:x.append(x[-1]+x[-2])or x,[[0,1]]*n)[0]
def f(n):a=0;b=1;exec'print a;a,b=b,a+b;'*n

I've never abused reduce so badly.

share|improve this answer
    
+1 for reduce abuse –  Warren P Jun 1 '12 at 21:34

C99, 58 characters

The following function fills an array of integers with the first n values from the Fibonacci sequence starting with 0.

void f(int*a,int n){for(int p=0,q=1;n--;q+=*a++)*a=p,p=q;}

Test harness, taking n as a command line argument:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
     int n = (argc > 1) ? atoi(argv[1]) : 1;
     int a[n];
     f(a, n);
     for (int i = 0; i < n; ++i)
          printf("%d\n", a[i]);
}
share|improve this answer

FALSE

0 1- 1 10[$][@@$@+$." "@1-]#
share|improve this answer

I am learning Lua so I would like to add this language to the pool.

Lua

function f(x)
    return (x<3) and 1 or f(x-1)+f(x-2)
end
for i=1,io.read() do
    print(f(i))
end

and the whole thing took 85 characters, with the parameter as a command line argument. Another good point is that is easy to read.

share|improve this answer

CoffeeScript, 48

f=(n,i=1,j=1)->(console.log i;f n-1,j,i+j)if n>0

65 in js:

function f(n,i,j){if(n>0)console.log(i),f(n-1,(j=j||1),(i||1)+j)}
share|improve this answer

PHP, 87

function f($n,$a=array(0,1)){echo' '.$a[0];$n>0?f(--$n,array($a[1],array_sum($a))):'';}

Uses array_sum and recursive function to generate series.

Eg:

 $ php5 fibo.php 9
 0 1 1 2 3 5 8 13 21 34 
share|improve this answer

F#, 123

let f n = Seq.unfold(fun (i,j)->Some(i,(j,i+j)))(0,1)|>Seq.take n
f 5|>Seq.iter(fun x->printfn "%i" x)
share|improve this answer

Scala, 65 characters

(Seq(1,0)/:(3 to 9)){(s,_)=>s.take(2).sum+:s}.sorted map println

This prints, for example, the first 9 Fibonacci numbers. For a more useable version taking the sequence length from console input, 70 characters are required:

(Seq(1,0)/:(3 to readInt)){(s,_)=>s.take(2).sum+:s}.sorted map println

Beware the use of a Range limits this to Int values.

share|improve this answer

Q 24

f:{{x,sum -2#x}/[x;0 1]}

First n fibonacci numbers

share|improve this answer

Haskell (26)

Surprisingly, this is only one character longer than the J solution.

f=(`take`s)
s=0:scanl(+)1s

I shave off a few characters by:

  1. Using take as a binary operator;
  2. Using scanl instead of the verbose zipWith.
share|improve this answer

dc, 32 characters:

This will actually always show the two first 1's, so the function only work as expected for N >= 2.

?2-sn1df[dsa+plarln1-dsn0<q]dsqx

C, 75 characters:

Not as cool as the accepted answer, but shorter and way faster:

main(n,t,j,i){j=0,i=scanf("%d",&n);while(n--)t=i,i=j,printf("%d\n",j+=t);}
Extra:

CL, 64 characters:

One of my most used bookmarks this semester has an interesting example which is shorter than many some of the other ones here, and it's just a straight-forward invocation of the loop macro -- basically just one statement! Stripped it for all the whitespace I could:

(loop repeat n for x = 0 then y and y = 1 then(+ x y)collect y)

Quite short, and nice and readable! To read input, n (including surrounding whitespaces) can be replaced with (read), adding 3 characters.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.