# 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. – Zsolt Szilagy Aug 11 '20 at 11:57

# Arn, 5 bytes

Since I finally implemented sequences in my interpreter this is now a valid submission :)

╔Tò”7


# Explained

Unpacked: [1 1{+

[ Sequence...
1 1 ...with 2 values initialized at 1...
{ ...the rest of which are determined by the block...
+ ...that adds the top two values
} Implied, can be removed
] Implied, can be removed


Since Arn supports infinite sequences and BigNums, this will continuously output fibonacci numbers infinitely (hypothetically)

# Barrel, 26 bytes

Disclaimer: The language is newer than the question, but I didn't even think of golfing this until after I'd created the language. I did update the language after I originally wrote the answer, and changed my answer, but that was because I was fixing the interpreter and made some changes to the spec to make the language work better. I wasn't cheating, I promise :)

+&1:0¤n &0:@1&1:a#@0+←1


Explanation:

+                          // set the accumulator to one by incrementing (initialization)
&1:0                      // set register 1 to value 0 (initialization)
¤               ←1   // define a target that can be jumped to; then, jump to the previously defined jump target
n                    // print the accumulator as a number and implicitly print the following space
&0:@1              // set register 0 to register 1
&1:a          // set register 1 to the value of the accumulator
#         // for as many times...
@0       //     ... as [value of register 0]...
+      //         ... increment the accumulator


I find it a bit hard to explain this further, so here's a rough chart of the accumulator and the two registers used during execution which will hopefully remove any confusion:

acc   reg[0]    reg[1] |
---------------------- |
1     <uninit>  0      | initialize; print acc("1")
1     0         1      | set reg[0] to reg[1]; set reg[1] to acc
1     0         1      | add reg[0] to acc; jump back and print acc ("1")
1     1         1      | set reg[0] to reg[1]; set reg[1] to acc
2     1         1      | add reg[0] to acc; jump back and print acc ("2")
2     1         2      | set reg[0] to reg[1]; set reg[1] to acc
3     1         2      | add reg[0] to acc; jump back and print acc ("3")
3     2         3      | set reg[0] to reg[1]; set reg[1] to acc
5     2         3      | add reg[0] to acc; jump back and print acc ("5")
5     3         5      | set reg[0] to reg[1]; set reg[1] to acc
8     3         5      | add reg[0] to acc; jump back and print acc ("8")


...and so forth and so on.

• Added the bounty! Also, you don't need the disclaimer, there used to be a rule banning languages newer than the challenge but it was removed a while back :) – Redwolf Programs Apr 14 at 1:52

# Pinecone, 35 bytes

b:0;a:1;tru@(print:a;t:a;a:a+b;b:t)


• How did you get to know Pinecone? For me it was because I wanted to learn how to make my own language – Recursive Co. Apr 21 at 16:14
• @ophact I was researching on creating Lexers, and I found an article on it, that's how i reached there :) – wasif Apr 21 at 16:15

# Red, 47 bytes

F: func[N][either N < 2[n][(F N - 2)+ F N - 1]]


Try it online!

## Bash 100

This is a very slow, but hey no performance penalty. First line needed.

#!/bin/bash
if [ $1 -lt 2 ]; then echo$1; exit; fi
expr $0 \expr$1 - 1\ + $0 \expr$1 - 2\

• More a question: You don't need a shebang, do you? See ruby, python and xy-script. – user unknown Apr 12 '11 at 1:39

# Vitsy, 11 Bytes

I'm certain there's a way to shorten these.

Print out all fibonacci (to Integer.MAX_VALUE)

01[D}+DNaO]
01          Push 0 and 1 to the stack.
[       ] Repeat infinitely.
D        Duplicate the top item of the stack.
}       Rotate the stack to right.
+      Add the top two items.
D     Duplicate the top item.
N    Print the top item out as a number.
aO  Print a return.


Print out to input fibonacci (13 bytes):

01}\[D}+DNaO]
01            Push 0 and 1 to the stack.
}\[       ] Get the input and repeat that many times.
D        Duplicate the top item of the stack.
}       Rotate the stack to right.
+      Add the top two items.
D     Duplicate the top item.
N    Print the top item out as a number.
aO  Print a return.


## Minkolang 0.10, 10 bytes

This language was created after this challenge but not for it.

Stream (link, do not click "Run"):

01d1R+dN2@


A mite clever, if I do think so. The 2@ at the end is a 2-trampoline that jumps over the 01 at the beginning, allowing the sequence to rise unabated.

01nd,7&[d1R+]rN.


Worse than I expected, 16 bytes. 01 sets it up, nd,7&...N. prints out 0 if the input is 0 and does the loop otherwise. [d1R+] builds up the sequence, then r reverses the stack and the correct number is outputted and the program ends with N..

• Grar! Again? You beat me by one again. grumble – Addison Crump Oct 30 '15 at 20:26
• .... ¯\_(ツ)_/¯ – El'endia Starman Oct 30 '15 at 20:38

# Turing machine code, 389

I wrote this the other day and decided to post it. Generates an infinite Fibonacci sequence in unary on the tape. See a commented version in action here.

0 _ 1 r 1
1 _ _ r 2
2 _ 0 r 3
3 _ _ r 4
4 _ 0 l 5
5 0 * l 5
5 _ * l 5
5 1 * r f
a 0 1 r b
b 0 * r b
b _ * r c
c 0 * r c
c _ * r d
d _ 0 l e
e 0 * l e
e _ * l e
e 1 * r f
f 0 1 r g
f _ * r k
g 0 * r g
g _ * r h
h 0 * r h
h _ * r i
i 0 * r i
i _ 0 l j
j 0 * l j
j _ * l j
j 1 * r f
k 0 1 r l
k _ * l R
l 0 * r l
l _ * r m
m 0 * r m
m _ 0 l n
n 0 * l n
n _ * l n
n 1 * r k
R _ * r a
R 1 0 l R


# ShapeScript, 16 14 bytes

_1@0@'@1?+'*!#


This reads an integer n (in unary) from STDIN and prints the nth Fibonacci number.

The submission is non-competing, since this challenge predates ShapeScript's creation by a few years.

Try it online!

### How it works

        Input: a string of n 1's
_       Get the length of the input to push n.
1@      Swap it with 1 (F[-1]).
0@      Swap it with 0 (F[0]).
STACK: F[-1]   F[0]   n
'       Push a string that, when evaluated for the i-th time,
does the following:
@       Swap F[i-2] on top of F[i-1].
1?      Push a copy of F[i-1].
+       Add the copy of F[i+1] to F[i].
'       STACK: F[i-1]   F[i]
*!      Repeat the string n times and evaluate it.
#       Discard F[n] from the stack.


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


# Brainf*ck, 489 466 characters

Granted, this is a bit overkill, not to mention that it could be optimised a lot. I will get to improving it tomorrow, since it's too late today.

EDIT: Improved by a few bytes by putting stuff closer together on the tape.

++++++>++++++++++>+>>>>>>>>>+<<<<<<<<<<<[->>[>>+>+<<<-]>>>[<<<+>
>>-]<<+>[<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]+++++
+++[<++++++>-]>[<<+>>-]>[<<+>>-]<<]>]<[->>++++++++[<++++++>-]]<[
.[-]<]>>>>>>>>[->+<<<<<<<<<<+>>>>>>>>>]>[-<+>]<<<<<<<<<<<.>>>>>>
>>>>[>>+>+<<<-]>>>[<<<+>>>-]<<+>[<->[>++++++++++<[->-[>+>>]>[+[-
<+>]>+>>]<<<<<]>[-]++++++++[<++++++>-]>[<<+>>-]>[<<+>>-]<<]>]<[-
>>++++++++[<++++++>-]]<[.[-]<]<<<<<<<<<<[->+>>>>>>>>+<<<<<<<<<]>
[-<+>]<<.<]


# Oration, 135 bytes

I believe that this is "optimal"... takes a deep breath here we go!

Inhale
Start a function f with n
If n<2
Return n
Backtracking
Inhale
Here
Literally, f(n-2)+f(n-1)
I'm done
Listen
Invoke f with number


The little ~> is input. This outputs the (input)th Fibonacci number. This transpiles to (in Python):

def f(n):
if n<2:
return  n
return f(n-2)+f(n-1)
print(f(eval(input("~>"))))

• Why is the transpiled Python code not golfed D: – Downgoat Feb 2 '16 at 4:01

# Oracle SQL 9.2, 80 bytes

SELECT ROUND(POWER((1+SQRT(5))/2,LEVEL-1)/SQRT(5))FROM DUAL CONNECT BY LEVEL<:1;


# Lua, 51 bytes

function f(n) return n<2 and n or f(n-1)+f(n-2)end

It creates a function called f(n), that takes an input (n). If n = 1, returns n. This function uses recursion.

# beeswax, 12 bytes (sequence), 42 bytes (n-th Fib.)

Beeswax is newer than the question, so no competition here.

Fibonacci sequence.

p{N<P{*
>~+d


No promotion to higher bit widths implemented in my solution, so 64-bit overflow starts at the 93rd or 92nd Fibonacci number, depending if you start counting your sequence at 0 or 1:

0
1
1
2
3
5
8
13
21
34
55
89
.
.
.
4660046610375530309
7540113804746346429
12200160415121876738   ← 93rd Fibonacci number
1293530146158671551    ← 1st. 64-bit overflow/wraparound
13493690561280548289


N-th Fibonacci number:

;{#'<>~P~L#MM@>+@'p@{;
_TNX~P~K#{; d~@M<


The same limit applies to this solution.

# CJam, noncompeting, 11 bytes

0X{_@+}q~*;

• F(0) = 0. You should eliminate the backslash. – Dennis Mar 2 '16 at 15:40
• Ah I was assuming that we were starting from 1,1..... so I guess this is a good convention since it saves a byte :) – A Simmons Mar 2 '16 at 16:18
• People start the Fibonacci sequence at different values, so F(0) = 0 may or may not be defined. However, when it comes to indexing, F(1), F(2) = 1, since a lot of the sequence's properties depend on that. – Dennis Mar 2 '16 at 16:29

1$[^^+2!]!  Try it here. An infinite stream that leaves results on stack. Use the Step button to avoid setting off the infinite loop. # Explanation 1$         {start w/ 2 1's}
[     ]! {execute lambda}
^^      {take top 2 items on stack}
2!   {self recurse!}


# Gogh, 10 bytes

¹Ƥ{Ƥ÷®+Ø}x


Executed from the command line like this:

\$ ./gogh "" "¹Ƥ{Ƥ÷®+Ø}x"


### Explanation

¹       “ Push two ones to the stack.                 ”
Ƥ       “ Print the TOS.                              ”
{       “ Open a code block.                          ”
Ƥ      “ Print the TOS.                              ”
÷      “ Duplicate the TOS.                          ”
®      “ Rotate the stack leftward.                  ”
+      “ Destructively add the TOS to the STOS.      ”
Ø      “ Loop all preceding code (within the block). ”
}       “ Close a code block.                         ”
x       “ Execute the TOS.                            ”
`