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 '20 at 11:57

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

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

C, 33 bytes

Recursively calculates the nth fibbonacci number.

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


Mathematica, 32 26 bytes

-6 bytes thanks to @MartinEnder!

±1=±2=1;±n_:=±(n-1)+±(n-2)

Recursive function, returns nth value in sequence.

• You can golf this with prefix notation: f@1=f@2=1;f@n_:=f[n-1]+f[n-2]. And even further by defining an operator instead: ±1=±2=1;±n_:=±(n-1)+±(n-2). Mar 24 '17 at 9:57
• Oh yeah, forgot about prefix notation here. Didn't know about the operator, thanks! Mar 24 '17 at 11:06

JavaScript (ES6) - 24 Characters (non-competing)

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


JavaScript - 24 Characters (snippet)

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


Set a value for n and it will calculate the nth Fibonacci value.

• The JavaScript ES6 version should be non-competing as JavaScript ES6 was implemented after this challenge. Mar 25 '16 at 1:07
• Also, the second solution is invalid as it's a snippet and not a full program / function. Mar 25 '16 at 1:10

JavaScript (ES6)

A couple of different ES6 implementations. The first two return the nth Fibonacci number and the third returns an array of the first n Fibonacci numbers. Non-competing, obviously.

30 bytes

f=

(n,x=1,y=0)=>!n?y:f(n-1,x+y,x)

console.log(f(10))

46 bytes

f=

n=>(x=1,y=0,eval("while(n--)[x,y]=[x+y,x]"),y)

console.log(f(10))

46 bytes

f=

n=>(a=[],(f=x=>a[x]=x<2?x:f(--x)+f(--x))(n),a)

console.log(f(10))

Axiom, 113 bytes

f(n:NNI):NNI==(n=0=>0;n:=n-1;x:=sqrt(5);floor(numeric(((x+1)/(2*x))*((1+x)/2)^n+((x-1)/(2*x))*((1-x)/2)^n)))::INT


code for test and results

(80) -> [f(i)  for i in 0..20]
(80)
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
Type: List NonNegativeInteger
(81) -> f 100
(81)  354224848179261915076
Type: PositiveInteger
(82) -> f 200
(82)  280571172992510140037336354957747795525632
Type: PositiveInteger
(83) -> f 400
(83)
1760236806450139664680709294813170892283658770059881093310828506440687624218_
31925760
Type: PositiveInteger
(84) -> f 800
(84)
6928308186422471713609360660466569632290421684876894264783997577258487494487_
420363654234099779749410573113727333378633545181944038619446626409501657425_
3135847342735360
Type: PositiveInteger
(85) -> f 1500
(85)
1355112566856310195162377575526951323656561770431639555079987987810736653460_
922122221302671882558120755439823360357867711740787668744312284056217232330_
713983569575833249689158528416736647370129969548463847884661978641646883591_
466734576231634867107272686298047871451723693301109753896341229444935835304_
2229054930944
Type: PositiveInteger
(86) -> f 2000
(86)
4224696333392304878698067179976673472756391964001565086095500593531167791551_
743662247281607190958887487440686606420026093467732621145548367502217030083_
858092272596709322168369132666938424515347258074945014044152199085287931830_
556530989999311940427567701708311778838430925973655760228465275886647451746_
556255968313014088560151159533857580044154666168801306507492995800168547537_
206536250047308876795741658264221262020608


Tampio, 107 bytes

uni on 1 lisättynä 1:een lisättynä yhteenlaskuun sovellettuna unen jäseniin ja unen hännän jäseniin


Explanation:

uni on 1 lisättynä 1:een lisättynä
uni =  1 :         1     :

yhteenlaskuun sovellettuna  unen jäseniin ja unen hännän jäseniin
(+)           zip        (uni           ,  tail uni            )


Pylons, 13 bytes

Takes the number of iterations as a command line argument to the interpreter.

11fA..+@{A,i}


How it works:

11  # Pushes 1, 1 to the stack.
fA#.##.#+@  # Creates a function "A" that takes the top two elements of the stack and adds them.
{A,i}  # Calls A sys.argv[1] times.


Axiom, 35 bytes

a(0)==0;a(1)==1;a(n)==a(n-1)+a(n-2)


above it is one succession defined by Recurrence... Results

(7) -> [a(i)  for i in 0..20]
(7)  [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]

• ricorrence Recurrence? Sep 14 '17 at 4:20
• @MDXF thank you for the correction... Good morning
– user58988
Sep 14 '17 at 9:56

Pug, 30 bytes

Without input (infinite)

-a=b=1
while 1
=a
-b=a+(a=b)


Will produce an output:

1123581321345589144233377610...


With an output delimiter: 34 bytes

-a=b=1
while 1
=a+" "
-b=a+(a=b)


Will produce an output:

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


With HTML as an output delimiter: 31 bytes

-a=b=1
while 1
p=a
-b=a+(a=b)


Although I doubt this is compliant to the challenge's rules, this will produce:

<p>1</p>
<p>1</p>
<p>2</p>
<p>3</p>
<p>5</p>
<p>8</p>
<p>13</p>
<p>21</p>
<p>34</p>
<p>55</p>
...


With input (as a funcion; finite)

Without an output delimiter, 47 bytes

mixin f(n)
-a=b=1
while n--
=a
-b=a+(a=b)


For an input n=10, for example, it produces:

11235813213455


Just as it is with the infinite series versions:

• +4 bytes (+" ") = 51 bytes for a space delimiter
• +1 byte (p) = 48 bytes for an HTML <p> tag delimiter

Implicit, 12 11 bytes

]3.(,[+%:]ß


Try it online!

10 bytes (knock off the ß) if we don't need delimiters. It's not specified in the challenge... TIO

This is my own (rather simple) method of computing the sequence. Explanation:

#::.(,[+%:]ß
#::.            push 0, 0, 1 (push stack length, duplicate twice, increment last one)
(.......    forever (implicit ¶ at end of program)
,           swap top two stack values
[          pop stack into memory
+         add top two stack values
%        print
:       duplicate top of stack
]      push memory to stack
ß     print a space


In a normal language, say, C, it would look like this:

int x, y, z;
x = 0; y = 0; z = 1;

do {
swap(&y, &z);
x += y;
y = x;
printf("%d ",x);
} while (1);


Equivalence:

int x = 0, y = 0, z = 1;   // #::.
do {                       // (
swap(&y,&z);           // ,
// [ (z is ignored below)
x += y;                // +
y = x;                 // :
printf("%d ",x);       // %ß
// ] (z is ignored above)
} while (1);               // ¶


Here's how the stack looks after each operation that modifies it:

#  0
:  0 0
:  0 0 0
.  0 0 1

,  0 1 0
[  0 1
+  1
%  1
:  1 1
]  1 1 0

,  1 0 1
[  1 0
+  1
%  1
:  1 1
]  1 1 1

,  1 1 1
[  1 1
+  2
%  2
:  2 2
]  2 2 1

,  2 1 2
[  2 1
+  3
%  3
:  3 3
]  3 3 2

,  3 2 3
[  3 2
+  5
%  5
:  5 5
]  5 5 3

,  5 3 5
[  5 3
+  8
%  8
:  8 8
]  8 8 5

,  8 5 8
[  8 5
+  13
%  13
:  13 13
]  13 13 8

,  13 8 13
[  13 8
+  21
%  21
:  21 21
]  21 21 13

,  21 13 21
[  21 13
+  34
%  34
:  34 34
]  34 34 21


Golf notes:

• ]3. is shorter than #::. which is shorter than :0::1 which is shorter than :0:0:1.
• ß is shorter than @32.
• (... is shorter than :1(;...:1).

(ß, ¶, and implicit ¶ added during the writing of this program.)

Momema, 28 bytes

1 1z0-8*01+*1*00+*1-*0-9 9z1


Try it online! Outputs infinitely with a tab between numbers.

If no separator between numbers is required, you can save four bytes:

1 1z0-8*01+*1*00+*1-*0z1


Explanation

                                                     #  a = 0
1   1       #            [1] = 1                     #  b = 1
z   0       #  label z0: jump past label z0 (no-op)  #  while true {
-8  *0      #            output num [0]              #    print a
1   +*1*0   #            [1] = [1] + [0]             #    b = a + b
0   +*1-*0  #            [0] = [1] - [0]             #    a = b - a
-9  9       #            output chr 9                #    print '\t'
z1          #  label z1: jump past label z0          #  }


Reflections, 93 bytes

     \
/*\/#  (0:0\
* 0\_*;(0\/ :(0\
\     v/#@/_ /
\  (1/ 1)0)*
: \\/
\(1/


Test it!

Explanation:

Initialisation

Executing \*/(1\*/*\0\.

• * at (5|2) pushes 5×2=10 (\n)
• (1 moves the newline to stack 1
• * at (0|2) pushes 0×2=0 (F(-1))
• * at (1|1) pushes 1×1=1 (F(0))
• 0 moves these two values to stack 0

Loop

Executing v1):\(1/\\0)#/:(0\/_//\*@\0:(0#/\_*;(0\/.

• 1) pulls the newline from stack 1
• : duplicates it
• (1 moves the duplicate to stack 1
• 0) pulls the last result from stack 0
• # redefines (0|0)
• : duplicates the last result
• (0 moves the duplicate back to stack 0
• _ at (3|0) converts the last result to a list of digits
• * at (1|1) pushes 1×1=1
• @ prints the last result and a newline
• 0 pulls both values from stack 0
• : duplicates the top one (newer one)
• (0 pushes the duplicate back to stack 0
• # redefines (0|0)
• _ at (0|1) adds the two values together
• * at (1|1) pushes 1×1=1
• ; pops that again
• (0 pushes the new result to stack 0

Stax, 2 bytes

|5


Run and debug online!

Added for completeness. An internal that returns 0-indexed Fibonacci number.

Infinite sequence generator without using the internal:

ò¶AÄ∟


The ASCII equivalent is

01WQb+


SmileBASIC, 28 bytes

F.,1DEF F X,Y?Y
F Y,X+Y
END


Ungolfed:

F 0,1
DEF F X,Y
PRINT Y
F Y,X+Y
END


Elixir, 49 bytes

Defines a function to get the nth fibonacci number. 1-indexed (starts at 0).

Simple recursive formula. Slow.

def f(n)when n<2,do: n
def f(n),do: f(n-1)+f(n-2)


Try it online!

Elixir, 50 bytes

Returns an infinite stream of fibonacci numbers. 1-indexed (starts at 0).

Fast, carries over an accumulator with the sum of the previous two numbers.

fn->Stream.unfold{0,1},fn{a,b}->{a,{b,a+b}}end end


Try it online!

Javascript, 57 bytes

_=1;i=0;for(z=10;z--;)alert((a=>!(o=_+i)+(i=_)+!(_=o))())

Python 2, 33 31 bytes

i=j=1
while 1:print j;i,j=j+i,i


Try it online!

Uses a loop to infinitely print the sequence. Will eventually error out due to integer overflow. It has been pointed out to me that Python uses arbitrary precision integers. Learn something new every day!

• Python uses arbitrary precision integers so an integer overflow will not occur. Aug 3 '18 at 14:48
• i,j=1,1 can be i=j=1. Aug 3 '18 at 14:48

µ6, 16 bytes

[>#[,.[+.]][[,>[#/0[+/1]<>]]/1]]


Try it online!

Explanation

[>                               -- right element of the tuple generated by
#                              -- | primitive recursive function
-- | base case:
[,                            -- | | pair of
.                           -- | | | constant zero
[+.]                        -- | | | successor of constant zero
]                             -- | | : (0,1)
-- | recursive case:
[                             -- | | compose the two
[,                           -- | | | pair of
>                           -- | | | | the right element
[#/0[+/1]<>]                -- | | | | add left & right element
]                            -- | | | (snd, fst + snd)
/1                           -- | | | second argument (we only need the tuple)
]                             -- | : (f (n-1), f (n-2) + f (n-1))
]                                -- : f n


Julia 0.6, 19 bytes

!a=round(φ^a/√5)


Try it online!

This is 16 chars and 19 bytes, a goof way to abuse Julia beats the existing Julia answers which were 20 bytes. by 1 bytes and 3 chars

Tcl, 71 bytes (function implementation=43, Enter=1, call=27)

proc F x {expr $x>1?\[F$x-1]+\[F $x-2]:$x}
while 1 {puts [F [incr i]]}


Try it online!

Serves both purposes: Has a function F that allows calculate the x'th Fibonacci number. then it is called to show on stdout F applied to the whole range of positive integers.

• tcl,89: Different approach — iterative. demo — but it does not have a function and fails to represent the first one. Jul 8 '17 at 22:17
• Failed outgolf; tcl,91 (function implementation=56, Enter=1, call=34): tio.run/##K0nO@f@/oCg/WaEkOcfKKjexJCOtNC/… Nov 5 '17 at 17:08
• You can use less expr as there's a leading one, in escaping evaluation of each 1st brackets code 45B Dec 16 '18 at 20:00
• Thanks @david . I did not know I could do it by escaping [ with \. I bet I have some more answers I can golf them the way you described. Dec 16 '18 at 20:52

R, 37 bytes

Prints the n'th term using the closed form.

https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

function(n,s=5^.5)round((s/2+.5)^n/s)


Try it online!

C# (.NET Core), 68, 56 bytes

Lambda using decimal size for single n.

EDIT: Ty Jo King for pointing out better ways to assign the maths to the vars!

p=>{decimal a=0,b=1,j=0;for(;j++<p;b=a-b)a+=b;return a;}


Try it online!