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

Language: dc, Char count: 20

Shorter dc solution.

dc -e'1df[dsa+plarlbx]dsbx'

Answer 2

18 characters of English..

"Fibonacci Sequence"

ok, I fail. :)

Answer 3

13 chars of Golfscript:

2,~{..p@+.}do

---

Update to explain the operation of the script:

1. 2, makes an array of [0 1]
2. ~ puts that array on the stack
3. So, at the time we run the do, we start the stack off with 0 1 (1 at top of stack)

The do loop:

1. Each . duplicates the top item of the stack; here, we do this twice (leaving us with 0 1 1 1 on initial run)
2. p prints the topmost value (leaving us with 0 1 1)
3. @ rotates the top 3 items in the stack, so that the third-topmost is at the top (1 1 0)
4. + adds the top 2 items in the stack (leaving 1 1)
5. . duplicates the top value, so that the do loop can check its truthiness (to determine whether to continue)

Tracing this mentally a couple of loops will be enough to tell you that this does the required addition to generate the Fibonacci sequence values.

Since GolfScript has bignums, there will never be an integer overflow, and so the top-of-stack value at the end of the do loop will never be 0. Thus, the script will run forever.

Answer 4

@Andrea Ambu

An iterative pythonic fibonacci()'s version should look something like that:

def fibonacci(a=0, b=1):
    while True:
        yield b
        a, b = b, a+b

Answer 5

The previous Ruby example won't work w/o either semicolons or newlines, so it's actually 32 chars. Here's the first example to actually output the sequence, not just return the value of a specified index.

Ruby:
53 chars, including newlines:

def f(n);n<2?1:f(n-1)+f(n-2);end
0.upto 20 {|n|p f n}

or if you want function that outputs a usable data structure, 71 chars:

def f(n);n<2?1:f(n-1)+f(n-2);end
def s(n);(0..n).to_a.map {|n| f(n)};end

or accepting command-line args, 70 chars:

def f(n);n<2?1:f(n-1)+f(n-2);end
p (0..$*[0].to_i).to_a.map {|n| f(n)}

Answer 6

let rec f l a b =function 0->a::l|1->b::l|n->f (a::l) b (a+b) (n-1) in f [] 1 1;;

80 characters, but truly generates the sequence, in linear time.