# 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>

# Keg, 10 bytes

01{:. ,:"+


Endlessly outputs numbers separated by spaces

# How it works

0    Pushes 0
1    Pushes 1
{    Begins an endless while loop
:.   Outputs the top item of the stack
,   Outputs a space
:"   Duplicates the top item of the stack and puts it at the bottom
+    Adds the top two numbers of the stack


Try it Online!

# x86 Machine Code (ELF format) - 484 bytes

This program will calculate fibonacci digits until there is no memory left, so you might want to process the output to get Nth one you are looking for.

Offset(h) 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

00000000  7F 45 4C 46 01 01 01 00 00 00 00 00 00 00 00 00  .ELF............
00000010  02 00 03 00 01 00 00 00 C0 80 04 08 34 00 00 00  ........Ŕ€..4...
00000020  00 00 00 00 00 00 00 00 34 00 20 00 02 00 28 00  ........4. ...(.
00000030  00 00 00 00 01 00 00 00 00 00 00 00 00 80 04 08  .............€..
00000040  00 00 00 00 E4 01 00 00 00 10 00 00 05 00 00 00  ....ä...........
00000050  00 10 00 00 01 00 00 00 00 00 00 00 00 90 04 08  ................
00000060  00 00 00 00 00 00 00 00 00 00 10 00 06 00 00 00  ................
00000070  00 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00000080  51 B9 00 90 04 08 88 01 31 C0 BA 01 00 00 00 EB  Qą......1Ŕş....ë
00000090  03 51 89 C1 31 C0 89 C3 43 B0 04 CD 80 31 C0 99  .Q‰Á1Ŕ‰ĂC°.Í€1Ŕ™
000000A0  42 59 C3 00 00 00 00 00 00 00 00 00 00 00 00 00  BYĂ.............
000000B0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
000000C0  31 C0 99 42 B9 03 90 04 08 C6 41 01 0A C6 41 02  1Ŕ™Bą....ĆA..ĆA.
000000D0  01 C6 41 03 01 3A 71 03 0F 84 FF 00 00 00 3A 71  .ĆA..:q..„˙...:q
000000E0  03 74 26 80 41 03 05 0F B6 41 03 6B C0 08 00 41  .t&€A...¶A.kŔ..A
000000F0  04 8A 41 04 E8 87 FF FF FF 80 69 04 30 C6 41 03  .ŠA.č‡˙˙˙€i.0ĆA.
00000100  01 83 E9 03 3A 71 03 75 DA 8A 41 04 E8 6F FF FF  ..é.:q.uÚŠA.čo˙˙
00000110  FF 3A 71 06 0F 84 BA 00 00 00 0F B6 41 05 88 41  ˙:q..„ş....¶A..A
00000120  06 0F B6 41 07 88 41 05 0F B6 41 07 00 41 06 C6  ..¶A..A..¶A..A.Ć
00000130  41 07 00 3A 71 06 0F 84 88 00 00 00 C6 41 07 01  A..:q..„....ĆA..
00000140  FE 49 06 3A 71 06 0F 84 78 00 00 00 C6 41 07 02  ţI.:q..„x...ĆA..
00000150  FE 49 06 3A 71 06 0F 84 68 00 00 00 C6 41 07 03  ţI.:q..„h...ĆA..
00000160  FE 49 06 3A 71 06 0F 84 58 00 00 00 C6 41 07 04  ţI.:q..„X...ĆA..
00000170  FE 49 06 3A 71 06 74 4C C6 41 07 05 FE 49 06 3A  ţI.:q.tLĆA..ţI.:
00000180  71 06 74 40 C6 41 07 06 FE 49 06 3A 71 06 74 34  q.t@ĆA..ţI.:q.t4
00000190  C6 41 07 07 FE 49 06 3A 71 06 74 28 C6 41 07 08  ĆA..ţI.:q.t(ĆA..
000001A0  FE 49 06 3A 71 06 74 1C C6 41 07 09 FE 49 06 3A  ţI.:q.t.ĆA..ţI.:
000001B0  71 06 74 10 FE 41 08 FE 41 09 FE 49 06 0F B6 41  q.t.ţA.ţA.ţI..¶A
000001C0  06 88 41 07 C6 41 06 01 83 C1 03 3A 71 06 0F 85  ..A.ĆA...Á.:q..…
000001D0  46 FF FF FF 3A 71 03 0F 85 01 FF FF FF B3 00 31  F˙˙˙:q..….˙˙˙ł.1
000001E0  C0 40 CD 80                                      Ŕ@Í€


# Jasmin, 120 bytes

Defines a class F with a static method f that calculates the nth Fibonacci number. My implementation is essentially an iterative solution that stores partially computed Fibonacci numbers on the stack.

.class F
.super java/io/File
.method static f(I)I
ldc 0
ldc 1
dup_x1
iinc 0 -1
ifgt $-9 ireturn .end method  # Some interesting golfing tricks used 1. Extending java/io/File is shorter than extending java/lang/Object (The super line cannot be omitted). I've check and File is tied for the shortest fully qualified class name. 2. Making this an instance method would let me remove static from the method header but, then I would have to explicitly implement an empty constructor to make the function callable (costing quite a few bytes). 3. Juggling the Fibonacci values on the stack turned out to be shorter than storing them in local variables. 4. On the other hand it's worth storing the index in a local variable. This makes stack management easier (i.e. shorter) without too much extra length since there is an instruction for adding or subtracting from locals variables. 5. Although the JVM technically requires that you declare the maximum stack size before hand with .limit stack 5, this can be omitted if the class file is executed with the -noverify flag. I'm pretty sure this is some sort of undefined behavior but, it works in this this case. # Test setup To test the code you, need a main method to invoke the static method. class FibTest { public static void main(String[] args){ for(int i = 0; i < 20; i++){ System.out.println(F.f(i)); } } }  You then need to use jasmin.jar (obtained from the source forge linked in the title) to build F.class before building and executing the test file. Since the stack size was omitted, you need to execute the class with -noverify. The makefile below handles this. test: FibTest.class java -noverify FibTest FibTest.class: FibTest.java F.class javac FibTest.java F.class: F.j java -jar jasmin.jar F.j  # Brachylog, 10 bytes 0;1⟨t≡+⟩ⁱh  Try it online! Generates an infinite list of Fibonacci numbers through the output variable. # Brachylog, 14 12 bytes 0;1⟨{tẉ₂}↰+⟩  Try it online! Prints terms infinitely, separated by newlines. 0;1 Starting with [0,1], {tẉ₂} get and print the second element, + sum the two elements, ⟨ ↰ ⟩ and recur on the pair of those two values.  A variant to find the nth term of the sequence, 0-indexed: # Brachylog, 13 bytes ∧0;1⟨t≡+⟩ⁱ↖?t  Try it online! • An interesting (very slow) 12-byter, 0-indexed but wrong on element 0: {ḃ₁~clᵐ⌉<3}ᶜ – Unrelated String Nov 20 '19 at 23:45 # Brain-Flak, 3634 32 bytes ({}(())){({}[()]<(({})<>{})>)}<>  Outputs the nth number of the zero indexed Fibonacci sequence (F(0) = 1, F(1) = 1, etc.) Try it online! ## Explanation coming soon... # Gol><>, 7 bytes 12K+:N!  Byte knocked off courtesy of JoKing Try it online! 9 bytes 01T2K+:Nt  Outputs forever with newlines Try it online! • You don't need the leading 0, which means you can just strip out the teleporters and put a skip at the end instead. Try it online!. You can also do 1:@+:N! for the same amount of bytes if you prefer the stack not filling up – Jo King Oct 17 '19 at 0:54 # Taktentus, 87 bytes a:=1 @wy_n:=a @wy:=32 b:=1 n:=44 @>=n _:=@stop @wy_n:=a @wy:=32 c:=a a+=b b:=c n-- _-=8  n are variable how many times we count (n-1 because first are writing directly) # 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);}  ## Python (56 chars) n=input() x=5**0.5 print ((1+x)**n-(1-x)**n)/((2**n)*x)  And for the sequence n=input() i=1 x=5**0.5 while i<=n: print ((1+x)**i-(1-x)**i)/((2**i)*x) i+=1  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

• – Jonathan Frech Aug 12 '18 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))))


## Javascript, 27 26 characters

for(a=b=1;--n;b+=t)t=a,a=b


In an interactive javascript command line (Like google chrome console) it'll print out the nth fibonacci term for n > 1. undefined for n=1, runs forever for n < 1.

### 41 characters

for(x=[1,1],y=1;n-++y;)x[y]=x[y-1]+x[y-2]


Saving the n (>=2) first terms in an array.

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...


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 '13 at 21:53
• Alright, I will update it. – user10766 Nov 27 '13 at 21:57
• Already fixed it for you - looks like someone approved my edit suggestion. – Iszi Nov 27 '13 at 22:05
• That was me - I went to fix it, and found you had already. – user10766 Nov 27 '13 at 22:06
• Ah. All good, then. Welcome to Code Golf! – Iszi Nov 27 '13 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. – lirtosiast Aug 8 '15 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.

# R - 39

Shortest - recursive, until SO:

f=function(i,j){cat(i);f(j,i+j)};f(1,1)


Until n:

i=j=1;for(x in 1:n){print(i);k=i;i=i+j;j=k}


or (a bit vectorized):

a=c(1,1);for(x in 1:n)print((a=c(a[2],sum(a)))[1])


or (without any loop or recursion):

a=c(1,1);sapply(1:n,function(i)a<<-c(a[2],sum(a)))[1,]


# CoffeeScript, 63 bytes

j=0;k=1;a=[];a=((i=j+k;k=j;j=i) for i in [0..prompt()]);alert a


# C, 45 bytes

Simple, iterative approach. Exits when signed integer overflows.

a;main(b){for(;b>0;printf("%d ",a=b-a))b+=a;}


Try it here.

• I seems to me you can remove b>0 condition. – sergiol Jul 8 '17 at 22:32

# Julia, 20 bytes

!n=n>1?!~-n+!~-~-n:n


Straightforward implementation of the recursive definition. No match for the matrix approach, but a lovely opportunity to abuse Julia's ability to redefine operators.

Try it online!

# Maple, 27 bytes

ifelse(n<3,1,f(n-1)+f(n-2))


Usage:

> f := n -> ifelse(n<3,1,f(n-1)+f(n-2));
> f(2);
1
> f(3);
2


# Python, 75 bytes

a=[1,1]
while True:
a.append(a[-1]+a[-2])
a.pop(0)
print(a[-2])


Yes, I know, way too big, but I don't know golfing languages that well.

• 1) while True can be replaced with while 1. 2) You only need one space of indentation. 3) The while loop contents can be replaced with print(a[0]);a=[a[1],sum(a)] (on the same line as the while statement). 4) The parentheses on the print call can be removed if you're using Python 2. With all these tricks applied: a=[1,1]\nwhile 1:print(a[0]);a=[a[1],sum(a)] (replace the '\n' with a literal newline). – Mego Nov 17 '16 at 13:41
• If you take Mego's approach you can replace a=[a[1],sum(a)] with a=a[1],sum(a) to save two bytes. This works because the comma creates an implicit tuple rather than a literal list. – Post Rock Garf Hunter Nov 17 '16 at 13:56
• The same can also be done with a=[1,1]. It can be shortened to a=1,1 – Post Rock Garf Hunter Nov 17 '16 at 14:00

# Ruby (as function) 31 bytes

->n{a,b=1,0;n.times{a=b+b=a};b}

• This is byte-per-byte exactly the same as another answer. – Addison Crump Jan 18 '17 at 0:28
• Yes, it was. I commented on the other answer and wrote mine before the original author accepted my suggestion. Now I am only leaving the function, because I could not find any ruby function in 5 randomly-sorted pages of answers. – G B Jan 19 '17 at 7:13
• @VoteToClose Duplicate answers are allowed. – James Jan 19 '17 at 7:17
• My code was mostly stolen from the other answer, with a little improvement (which is now also in the original post), and my answer was written much later. I am leaving the function because I could not find another. – G B Jan 19 '17 at 7:28

# C, 33 bytes

Recursively calculates the nth fibbonacci number.

f(n){return n>1?f(n-1)+f(n-2):n;}