# Fibonacci function or sequence

The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1. Here are the first few terms:

1 1 2 3 5 8 13 21 34 55 89 ...


Write the shortest code that either:

• Generates the Fibonacci sequence without end.

• Given n calculates the nth term of the sequence. (Either 1 or zero indexed)

You may use standard forms of input and output.

(I gave both options in case one is easier to do in your chosen language than the other.)

For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});
else console.log(body);
});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();

languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body {
text-align: left !important;
display: block !important;
}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

• I am sort of waiting for a response like "f", 1 byte, in my math based golf language. Aug 11, 2020 at 11:57
• @ChrisJesterYoung can we use 1.0 are 1 only? May 11 at 2:45
• @NumberBasher 1.0 is fine. May 20 at 19:10

# dc, 21 17 bytes

0z[dp_3R+lmx]dsmx


Try it online!

This prints the Fibonacci sequence endlessly.

My previous (21-byte) version accepted an input $$\n\$$ on stdin, outputting the $$\n^\text{th}\$$ Fibonacci number on stdout (1-indexed):

9k5v1+2/?^5v/.5+0k1/p

# Actually, 16 bytes

"1,"◙01W;a+;◙',◙


Try it online!

# GAS x86-64 for Linux (Machine code), 76 68 bytes

### Loop-free, because I thought it would be a fun idea. GCC 10.1.

Note/warning: for this to work, you have to turn off DEP and PIE (ASLR). See compilation instructions below.

Look, ma! No loops! Byte count is for the assembled opcodes of func + e + f. Works on 32 bit input. Sure, you'll eventually run out of stack space, but the number will overflow before then. Obviously, a loop would have been much smaller (and easier) to write.

How it works:

1. Copy payload code to stack-relative space (No modification of %rsp)
3. Payload calculates the Fibonacci number in %rax and self-unwinds without ever looping

### Full testing program:

// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
.global main

message: .asciz "%d"
main:
mov $N, %rdi call func mov %eax, %esi mov$message, %rdi
xor %eax, %eax
call printf
xor %eax, %eax
ret

func:
// We'll take %rdi, but we'll slice it to 32 bits
// %edi is arg, r8d is our counter.
mov %edi, %r8d
// Make 2 copies for arithmetic
mov %r8d, %eax
// Set up stack offset
// N * 32, need 64 bits to work with %rsp
imul $(eof - e), %eax neg %rax mov %rsp, %r9 lea (%rax, %r9), %r9 // Initialize for Fibonacci xor %ebx, %ebx xor %eax, %eax inc %eax // Copy initial payload: // Because PIE is turned off, we can use 32-bit addressing for local // Stack still seems to be in 64-land, however mov$e, %esi
mov %r9, %rdi
mov $(eof - e), %ecx rep movsb // Go to stack offset jmp *%r9 e: // The payload: dec %r8d jg f ret f: // Do actual Fibonacci stuff lea (%ebx, %eax), %edx mov %eax, %ebx mov %edx, %eax // Self-replicate mov %r9, %rsi mov$(eof - e), %cl
rep movsb
eof:


I decided on 32-bit input because the stack is not all valid for 64 bits, so we'd run out anyway. It overflows after a we get high enough input, but that's expected.

### Compilation:

# Prints 55
# Replace 10 with the input number (1-indexed):
gcc -no-pie -z execstack execstack_fibonacci.sx -DN=10 -g

• The -z execstack tells the linker to turn off DEP for this program. (Allow the stack to be executable)
• The -no-pie turns off ASLR.
• The -DN10 is just easy input control.
• The -g is for debugging control. Turn it off if you want.

Note: this will NOT work in MinGW because the DEP policy is managed by the OS on Windows. In fact, -z isn't even recognized by MinGW's ld.

### Hex dump:

funcs='func e f'
for el in $funcs; do echo 'Dump$el'
gdb -batch -ex "disas/r $el" ./a.out | sed '/^$/d'
done
gdb -batch -ex "print eof - e" ./a.out

• You may be able to save quite a few bytes here, as there are a lot of unnecessary REX prefixes, and there isn't nearly enough push/pop abuse. Jan 16, 2021 at 14:56

# Javascript, 24 bytes - recursive version, 33 bytes - usage of Binet's formula, 46 bytes - continuous approximation with the "phi" itself

Usage of "Binet's formula" and a bitwise "OR" operator to round the result. Originally in the "Binet's formula" you have to subtract the so-called "smaller phi to the n-th power". "Smaller phi" (-0.618...) is inside the (-1;1) interval, so it gets closer to 0 with each positive power - that's why we can leave it, and just round the meaningful part. Function itself is an anonymous one, declared with the arrow function declaration.

n=>(((5**.5/2+.5)**n)/5**.5)+.5|0


Try it online!

Recursive version - arrow function declaration. Check whether n is less than 3, if so return 1, else do it again (at least) 2 more times, but with an argument of value n-1 and n-2:

f=n=>n<3?1:f(n-1)+f(n-2)


Try it online!

Continuous approximation. Ni * phi = Ni+1.

WARNING - RUNNING THIS CODE WILL END UP AS AN INFINITE AMOUNT OF ALERTS (next after clicking "ok")

f=n=>{l=n/2+5**.5/2*n+.5|0;alert(l);f(l)};f(1)

# BRASCA, 13 bytes

After being inactive here for god knows how long, I built a little esolang and decided to put it to the test.

Outputs each number seperated by newline.

nlo1[:n:R+lo]


## Explanation

n                   - Output 0 as number (an empty stack always pops zero)
lo                 - Push 10 (line feed) to the stack and print it
1                - Push 1 to the stack
[       ]       - While not zero:
:n             -   Output the number
:R+          -   Add it with the previous number
lo        -   And print another line feed


Github Repo

# Pxem, Filename: 29 bytes + Content: 0 bytes = 29 bytes.

Outputs fibonacci sequence, separated with space.

• Filename (escaped): \001.rX\001.w.c.n.c.t.v.m.v.+ .oX.a
• Actual: .rX.w.c.n.c.t.v.m.v.+ .oX.a
• Content: empty.

Try it online!

XX.z
# push 1; push $(($(pop)*$(rand))) # NOTE rand pushes 0<=x<1 # NOTE null character cannot be used for filename .a\001.rXX.z # push 1; push 88; while [$(pop) -ne 0 ]; do
.aX\001.wXX.z
# Do I really need to explain more?
# Just read the specification; I am going to bed
# also a sequence .t.v.m.v is an idiom
# to move top item to bottom
.a.c.n.c.t.v.m.v.+ .oX.a


# V (vim), 32 bytes

i1
1<esc>qqkyjGp:s:\n:+
C<C-r>=<C-r>"
<esc>@qq@q


(don't)Try it online!

Prints the sequence forever.

Output is not visible on TIO, so here's the first 99 iterations: Try it online!

Last accurate value is $$\7540113804746346429\$$ after which it exceeds the integer limit.

# Duocentehexaquinquagesimal, 5 bytes

±∊YO$ Try it online! Link is to a version with output; this one just writes the sequence to memory. Outputs codepoints of the entire sequence. Stops eventually because of memory limitations. # Branch, 18 bytes 1XY[/x#^\yX^+Y10.]  Try it on the online Branch interpreter! Outputs infinitely. Eventually starts producing garbage values because long long int overflows but that seems to be acceptable. ## Explanation 1 Set the node's value to 1 XY Set the X and Y registers to 1 [ ] While value is not 0 (this will always be true in this program) /x# Move to the left child, set to the X register, and output as number ^\ Move to the parent and then right child (go to right sibling) yX Set to the Y register, then set the X register to that value ^+Y Move to root, sum the children (X + Y), and set the Y register 10. Place 10 and output as character; this also keeps the loop going  # C (clang), 797047 46 bytes y;z;main(x){for(;printf("%i ",z=x+y);y=z)x=y;}  Try it online! Uses a for-loop instead of a while-loop just because I use it more and doing while() gives the same byte count. Thanks to ceilingcat for golfing 9 bytes. Thanks to Jo King for golfing 23 bytes. Thanks to ceilingcat for golfing another byte. # Knight, 20 19 bytes ;=x=y 1W!Ox=y+x=x y  Try it online! -1 byte: W1;Ox -> W!Ox The "print infinitely" variant. (It will eventually overflow). It is a simple add and swap loop. Ungolfed: # init x and y to 1 ; = x (= y 1) # loop forever # since OUTPUT evaluates to NULL, we # can just invert the condition : WHILE !(OUTPUT x) { # Add and swap : = y + x (= x y) }  # Python 3, 46 44 bytes lambda n,a=5**.5:((.5+a/2)**n-(.5-a/2)**n)/a  Try it online! Uses Binet's formula to derive the nth Fibonacci number. Very wrong answer from me misreading the question: g=lambda n:n+g(n-1)if n else n  Try it online! • The logic is right, but it does start to drift pretty quickly due to floating point errors. I'm not sure if this is 100% Kosher. Oct 7, 2021 at 11:26 • Fair. It's probably fine but it was not specified, so I guess we're in the dark. Oct 7, 2021 at 11:32 # Rattle, 9 bytes +s[p+~$]0


Try it Online!

Note: the link only runs this loop 100 times instead of infinitely because the online interpreter behaves strangely with an infinite loop for this code (which is a problem with the website, not the interpreter).

# Explanation

+s           increment the top of the stack (to 1) and save to memory
[    ]0    infinite loop
p         print top of stack
+~       increment top of stack by the value in storage
$swap the value on top of the stack with the value in storage  # Mascarpone, 45 bytes v['1.]v*'b<^[v{^vv'b>'a<[ab]v*'b<^a' .:!]v*:!  Try it online! Outputs the numbers in unary, separated by newlines. High-level explanation (go read the language specification first): I redefine the interpreter to have two symbols, a and b, which kind of act as variables. Each symbol's operation prints a certain amount of 1s, so they kind of act as numbers in unary, and the operation corresponding to the string ab prints out the sum of a and b. At the start, a corresponds to 0 and b is 1. Each step, I simultaneously redefine (a, b) = (b, a+b) and then I output the new value of a. Slightly less high-level explanation: I will replace the newline with N because its only function is to help push a newline character — it doesn’t actually do anything special in terms of the logic of the program. Due to the longness of the program, I’ll divide this explanation up into parts. The beginning: v['1.]v*'b<^  This changes the current interpreter so that the symbol b corresponds to the operation of outputting a single 1. (a corresponds to a no-op by default, so it doesn’t have to be mentioned here). The rest of the program: I will use the notation [x] (where x can be any character) to mean “the operation the current interpreter associates with the symbol x’, since that’s a lot to type and I don’t have much margin space to write the explanation in. [v{^vv'b>'a<[ab]v*'b<^a'N.:!]v*:! [ :!]v*:! Loop forever: v{^ Hard to explain v Create a new interp, 'a< where a is assoc with v'b> [b] 'b< and b is assoc with [ab]v* [ab] (i.e. [a], then [b]) ^ Set current interp := that interp a Now run the op corresponding to a 'N. and print a trailing newline.  # flax, 3 bytes 1+ⁿ  Port of the Jelly answer. Takes input from stdin. Works similarly to the Jelly answer. # Prolog, 63 bytes f([]). f([1,1]). f([X|[Y|[Z|L]]]):- f([Y|[Z|L]]), X is Y+Z.  # HOPS, 10 bytes seq(x+x^2) Attempt This Online! # HOPS, 11 bytes 1/(1-x-x^2) Attempt This Online! The generating function of the Fibonacci sequence is $$\1/(1-x-x^2)\$$. In HOPS, seq(f) means 1/(1-f). # C / Objective-c, 62 c;f(a,b){printf("%d ",a+b);if(c++<40)f(a+b,a);}main(){f(0,1);}  This will print the first 40 fibonacci numbers. I assume the compiler will set c=0. If it is trash, than it will not work; This version is smaller, but it infite show all sequence number # C / Objective-c, 50 (infinite) f(a,b){printf("%d ",a+b);f(a+b,a);}main(){f(0,1);}  • Variables with static duration are zero-initialized if not explicitly initialized. This behavior is required by the standard. Jul 30, 2021 at 17:48 PHP, Finite - 46 chars <?for($b=1;$i++<$n;)echo$b-$a=($b+=$a)-$a," ";  where$n is the length of the sequence

PHP, Infinite - 39 chars

<?for($b=1;;)echo$b-$a=($b+=$a)-$a,"
";


# MATLAB/Octave, n first numbers, 41 39 chars

a=0:1;for(i=3:n);a(i)=a(i-2)+a(i-1);end


# Python 3 (53)

def f(n):
l,p=0,1
while n:n,l,p=n-1,p,l+p
return l

• Aug 12, 2018 at 17:31

Clojure, 46

(defn f[x y z](if(= 0 z)x(recur y(+ y x)(- z 1))))


Although, technically 50 since Clojure requires the recur for pseudo tail call:

(defn f[x y z](if(= 0 z)x(recur y(+ y x)(- z 1))))


Non compressed:

(defn fib [left right iteration]
(if (= 0  iteration)
left
(fib right (+ right left)  (- iteration 1))))


It almost feels like cheating to use Haskell for something like this. It just prints Fibonacci numbers ad infinitum.

f=1:scanl(+)1f
main=print f


And if using GHCi only 21 characters, including two newlines, are necessary:

Prelude>let f=1:scanl(+)1f
Prelude>f
[1,1,2,3,5,8,13,21...

• this solution was already posted here. FYI. Nov 28, 2017 at 10:49

JAVA - 108 characters:

int[]f={0,1};System.out.println(0);for(int i=0;i<9;i+=2)System.out.printf("%d\n%d\n",f[0]+=f[1],f[1]+=f[0]);

• If a space is required in the code, it should be included in the character count.
– Iszi
Nov 27, 2013 at 21:53
• Alright, I will update it.
– user10766
Nov 27, 2013 at 21:57
• Already fixed it for you - looks like someone approved my edit suggestion.
– Iszi
Nov 27, 2013 at 22:05
• That was me - I went to fix it, and found you had already.
– user10766
Nov 27, 2013 at 22:06
• Ah. All good, then. Welcome to Code Golf!
– Iszi
Nov 27, 2013 at 22:10

# C 64 Characters

a;main(f,n){scanf("%d",&n);while(--n)f+=a=f-a;printf("%d",f-a);}


This will print the nth Fibonacci number.

a;
main(f,n){
scanf("%d",&n);
while(--n)
f+=a=f-a;
printf("%d",f-a);
}


F#, 63 chars:

let rec g x y n=if n=x then x else f (n-1) y (x+y)
let f=g 0 1


# ~-~! (No Comment) - 27

'=|*>~[<'&*-~>+<'&*-~~>]*|:


Didn't think it'd be this short.

# TI-BASIC - 18 symbols

to print fibonacci sequence starting from 0:

;i
;While 1
;Disp real(Ans
;real(Ans)+imag(Ans)+ireal(Ans
;End


to print fibonacci sequence starting from 1:

;1
;While 1
;Disp real(Ans
;real(Ans)+imag(Ans)+ireal(Ans
;End

• real(Ans)-conj(iAns is shorter. Aug 8, 2015 at 4:23

# Ruby - 49 characters

Nobody has done a Ruby solution for the second problem so I thought I'd give that a go:

p Hash.new{|h,k|k<2?k:(h[k-2]+h[k-1])}[gets.to_i]


# Javascript, 53 bytes

a=[1,1];setInterval('a.push(a[b=a.length-1]+a[b-1])')


I decided to use a new approach to create an infinite stream. Works anywhere else but Firefox.

To get the array of integers, simply do a from the console.