Fibonacci Code Golf

Question

Generate the Fibonacci sequence in the fewest amount of characters possible. Any language is OK, except for one that you define with one operator, f, which prints the Fibonacci numbers.

Starting point: 25 14 characters in Haskell:

f=0:1:zipWith(+)f(tail f)

f=0:scanl(+)1f

Answer 1

Generate the Fibonacci sequence. sequence SEQUENCE!

Answer 2

PDP-11 Assembler (source)

    .globl  start
    .text
start:
    mov $0,(sp)
    mov $27,-(sp)
    jsr pc, lambda
print_r1:
    mov $outbyte,r3
div_loop:
    sxt r0
    div $12,r0
    add $60,r1
    movb    r1,-(r3)
    mov r0,r1
    tst r1
    jne div_loop
    mov $1,r0
    sys 4; outtext; 37
    mov $1,r0
    sys 1
lambda:
    mov 2(sp),r1
    cmp $2,r1
    beq gottwo
    bgt gotone
    sxt r0
    div $2,r0
    tst r1
    beq even
odd:
    mov 2(sp),r1
    dec r1
    sxt r0
    div $2,r0
    mov r0,-(sp)
    jsr pc,lambda
    add $2,sp
    mov r0,r3
    mov r1,r2
    mov r3,r4
    mul r2,r4
    mov r5,r1
    mov r3,r4
    add r2,r4
    mul r2,r4
    add r5,r1
    mul r3,r3
    mov r3,r0
    mul r2,r2
    add r3,r0
    rts pc
even:
    mov 2(sp),r1
    sxt r0
    div $2,r0
    dec r0
    mov r0,-(sp)
    jsr pc,lambda
    add $2,sp
    mov r0,r3
    mov r1,r2
    mov r2,r4
    mul r2,r4
    mov r5,r1
    mov r2,r4
    add r3,r4
    mul r4,r4
    add r5,r1
    mov r2,r4
    add r3,r4
    mul r2,r4
    mov r5,r0
    mul r2,r3
    add r3,r0
    rts pc
gotone:
    mov $1,r0
    mov $1,r1
    rts pc
gottwo:
    mov $1,r0
    mov $2,r1
    rts pc

    .data
outtext:
    .byte 62,63,162,144,40,106,151,142,157,156
    .byte 141,143,143,151,40,156,165,155
    .byte 142,145,162,40,151,163,40
    .byte 60,60,60,60,60
outbyte:
    .byte 12

Answer 3

J, 27 characters for a non-recursive function:

f=:3 :'{:}.@(,+/)^:y(0 1x)'

+/ sums over a list.
(,+/) appends the sum of a list to its tail.
}.@(,+/) sums a list, appends an element to its tail, and drops the first element.
}.@(,+/)^:y iterates the above function y times.
}.@(,+/)^:y(0 1x) applies the above function to the list (0,1) (the x makes it an integer).
{:}.@(,+/)^:y(0 1x) takes the last element of the output list of the above.
f=:3 :'{:}.@(,+/)^:y(0 1x)' defines f to be a function on one variable y.

Answer 4

Corrected after comments (thanks Sebastian), it wasn't a sequence solution, so here we go with 42 chars (includes the \n):

def f(a=0,b=1):
 while 1:yield a;a,b=b,a+b

---

OLD post below

Python, 38 chars.

f=lambda n:n if n<2 else f(n-1)+f(n-2)

Not so short but the most readable in my opinion :P

EDIT: Here is the analytic way (if someone needs to see it in python :-)

f=lambda n:int(.5+(.5+5**.5/2)**n/5**.5)

Answer 5

Here's my best using scheme, in 45 characters:

(let f((a 0)(b 1))(printf"~a,"b)(f b(+ a b)))

Answer 6

RePeNt, 9, 8 chars

1↓[2?+1]

Or 10 chars with printing:

1↓[2?+↓£1]

Run using:

RePeNt "1↓[2?+1]"

RePeNt is a stack based toy language I wrote (and am still improving) in which all operators/functions/blocks/loops use Reverse Polish Notation (RPN).

Command      Explanation                                              Stack
-------      -----------                                              -----

1            Push a 1 onto the stack                                  1
↓            Push last stack value                                    1 1
[            Start a do-while loop                                    1 1
2?           Push a two, then pop the 2 and copy the last 2 stack     1 1 1 1
             items onto the stack
+            Add on the stack                                         1 1 2
↓£           Push last stack value then print it                      1 1 2
1            Push a 1 onto the stack                                  1 1 2 1
]            Pop value (1 in this case), if it is a 0 exit the loop   1 1 2
             otherwise go back to the loop start.

The answer is on the stack which builds itself up like:

1 1
1 1 2
1 1 2 3
1 1 2 3 5

It never terminates (it has the eqivilent of a C#/JAVA do { } while(true) loop) because the sequence will never terminate, but a terminating solution can be written thus:

N_1↓nI{2?+}

which is 12 chars.

I wonder if anyone will ever read this :(