[Question]
  [
The [Fibonacci sequence](http://oeis.org/A000045) 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 `n`th 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.
---
### Leaderboard
```
/* 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 ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}
function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
  return a.owner.display_name;
}
function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      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],
        link: a.share_link,
      });
    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;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);
    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)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }
}
```
```
body {
  text-align: left !important;
  display: block !important;
}
#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}
#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}
table thead {
  font-weight: bold;
}
table td {
  padding: 5px;
}
```
```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">
    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">
    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```
  
[Answer]
## Brainfuck, 22 bytes
```
+>++[-<<[->+>+<<]>>>+]
```
Generates the Fibonacci sequence gradually moving across the memory tape.
[Answer]
## Haskell, ~~17~~ ~~15~~ 14 bytes
```
f=1:scanl(+)1f
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P83W0Ko4OTEvR0Nb0zDtf25iZp6CrUJBUWZeiYJGSWJ2qoKhgYGCikKa5n8A "Haskell – Try It Online")
[Answer]
# Perl 6, 10 chars:
Anonymous infinite fibonacci sequence list:
```
^2,*+*...*
```
Same as:
```
0, 1, -> $x, $y { $x + $y } ... Inf;
```
So, you can assign it to an array:
```
my @short-fibs = ^2, * + * ... *;
```
or
```
my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;
```
And get the first eleven values (from 0 to 10) with:
```
say @short-fibs[^11];
```
or with:
```
say @fibs[^11];
```
Wait, you can get too the first 50 numbers from anonymous list itself:
```
say (^2,*+*...*)[^50]
```
That returns:
```
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
63245986 102334155 165580141 267914296 433494437 701408733 1134903170 
1836311903 2971215073 4807526976 7778742049
```
And some simple benchmark:
```
real    0m0.966s
user    0m0.842s
sys     0m0.080s
```
With:
```
$ time perl6 -e 'say (^2, *+* ... *)[^50]'
```
EOF
[Answer]
## C# 4, 58 bytes
**Stream (69; 65 if weakly typed to `IEnumerable`)**
(Assuming a `using` directive for `System.Collections.Generic`.)
```
IEnumerable<int>F(){int c=0,n=1;for(;;){yield return c;n+=c;c=n-c;}}
```
**Single value (58)**
```
int F(uint n,int x=0,int y=1){return n<1?x:F(n-1,y,x+y);}
```
[Answer]
## GolfScript, 12
Now, just 12 characters!
```
1.{[[email protected]](/cdn-cgi/l/email-protection)+.}do
```
[Answer]
# [Hexagony](https://github.com/mbuettner/hexagony), ~~18~~ ~~14~~ 12
Thanks Martin for 6 bytes!
```
1="/}.!+/M8;
```
Expanded:
```
  1 = "
 / } . !
+ / M 8 ;
 . . . .
  . . .
```
[Try it online](http://hexagony.tryitonline.net/#code=MT0iL30uISsvTTg7&input=)
---
Old, answer. This is being left in because the images and explanation might be helpful to new Hexagony users.
```
!).={!/"*10;$.[+{]
```
Expanded:
```
  ! ) .
 = { ! /
" * 1 0 ;
 $ . [ +
  { ] .
```
This prints the Fibonacci sequence separated by newlines.
[Try it online!](http://hexagony.tryitonline.net/#code=ISkuPXshLyIqMTA7JC5bK3td&input=) Be careful though, the online interpreter doesn't really like infinite output.
### Explanation
There are two "subroutines" to this program, each is run by one of the two utilised IPs. The first routine prints newlines, and the second does the Fibonacci calculation and output.
The first subroutine starts on the first line and moves left to right the entire time. It first prints the value at the memory pointer (initialized to zero), and then increments the value at the memory pointer by `1`. After the no-op, the IP jumps to the third line which first switches to another memory cell, then prints a newline. Since a newline has a positive value (its value is 10), the code will always jump to the fifth line, next. The fifth line returns the memory pointer to our Fibonacci number and then switches to the other subroutine. When we get back from this subroutine, the IP will jump back to the third line, after executing a no-op.
The second subroutine begins at the top right corner and begins moving Southeast. After a no-op, we are bounced to travel West along the second line. This line prints the current Fibonacci number, before moving the memory pointer to the next location. Then the IP jumps to the fourth line, where it computes the next Fibonacci number using the previous two. It then gives control back to the first subroutine, but when it regains control of the program, it continues until it meets a jump, where it bounces over the mirror that was originally used to point it West, as it returns to the second line.
---
Preliminary Pretty Pictures!
The left side of the image is the program, the right hand side represents the memory. The blue box is the first IP, and both IPs are pointing at the next instruction to be executed.
[![enter image description here](https://i.stack.imgur.com/tiqRU.gif)](https://i.stack.imgur.com/tiqRU.gif)
Note: Pictures may only appear pretty to people who have similarly limited skill with image editing programs :P I will add at least 2 more iterations so that the use of the `*` operator becomes more clear.
Note 2: I only saw [alephalpha's answer](https://codegolf.stackexchange.com/a/62716/31625) after writing most of this, I figured it was still valuable because of the separation, but the actual Fibonacci parts of our programs are very similar. In addition, this is the smallest Hexagony program that I have seen making use of more than one IP, so I thought it might be good to keep anyway :P
[Answer]
## J, 10 chars
Using built-in calculation of Taylor series coefficients so maybe little cheaty. Learned it [here](http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence#Generating_functions).
```
   (%-.-*:)t.
   (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075
```
[Answer]
# Python 2, 34 bytes
Python, using recursion... here comes a StackOverflow!
```
def f(i,j):print i;f(j,i+j)
f(1,1)
```
[Answer]
## [><>](http://esolangs.org/wiki/Fish) - 15 characters
```
0:nao1v
a+@:n:<o
```
[Answer]
## [COW](http://esolangs.org/wiki/COW), 108
```
 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 3 bytes
```
+¡1
```
[Try it online!](http://jelly.tryitonline.net/#code=K8KhMQ&input=MjA)
### How it works
```
+¡1    Niladic link. No implicit input.
       Since the link doesn't start with a nilad, the argument 0 is used.
  1    Yield 1.
+      Add the left and right argument.
 ¡     For reasons‡, read a number n from STDIN.
       Repeatedly call the dyadic link +, updating the right argument with
       the value of the left one, and the left one with the return value.
```
‡ `¡` peeks at the two links to the left. Since there is only one, it has to be the body of the loop. Therefore, a number is read from input. Since there are no command-line arguments, that number is read from STDIN.
[Answer]
# [Hexagony](https://github.com/mbuettner/hexagony), 6 bytes
```
1.}=+!
```
Ungolfed:
```
  1 .
 } = +
  ! .
```
It prints the Fibonacci sequence without any separator.
[Answer]
# Ruby, 29 27 25 24 bytes
```
p a=b=1;loop{b=a+a=p(b)}
```
Edit: made it an infinite loop. ;)
[Answer]
# Golfscript - single number - 12/11/10
12 chars for taking input from stdin:
```
~0 1@{.@+}*;
```
11 chars for input already on the stack:
```
0 1@{.@+}*;
```
10 chars for further defining 1 as the 0th Fibonacci number:
```
1.@{.@+}*;
```
[Answer]
# [Prelude](http://esolangs.org/wiki/Prelude), 12 bytes
One of the few challenges where Prelude is actually fairly competitive:
```
1(v!v)
  ^+^
```
This requires [the Python interpreter](https://web.archive.org/web/20060504072747/http://z3.ca/~lament/prelude.py) which prints values as decimal numbers instead of characters.
## Explanation
In Prelude, all lines are executed in parallel, with the instruction pointer traversing columns of the program. Each line has its own stack which is initialised to zero. 
```
1(v!v)
  ^+^
| Push a 1 onto the first stack.
 | Start a loop from here to the closing ).
  | Copy the top value from the first stack to the second and vice-versa.
   | Print the value on the first stack, add the top two numbers on the second stack.
    | Copy the top value from the first stack to the second and vice-versa.
```
The loop repeats forever, because the first stack will never have a `0` on top.
Note that this starts the Fibonacci sequence from `0`.
[Answer]
## DC (20 bytes)
As a bonus, it's even obfuscated ;)
```
zzr[dsb+lbrplax]dsax
```
EDIT: I may point out that it prints *all* the numbers in the fibonacci sequence, if you wait long enough.
[Answer]
**Mathematica, 9 chars**
```
Fibonacci
```
If built-in functions are not allowed, here's an explicit solution:
**Mathematica, ~~33~~ ~~32~~ 31 chars**
```
#&@@Nest[{+##,#}&@@#&,{0,1},#]&
```
[Answer]
# TI-BASIC, 11
By legendary TI-BASIC golfer Kenneth Hammond ("Weregoose"), from [this site](http://adriweb.free.fr/upload/ti/weregoose.html). Runs in O(1) time, and considers 0 to be the 0th term of the Fibonacci sequence.
```
int(round(√(.8)cosh(Anssinh‾¹(.5
```
To use:
```
2:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     1
12:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     144
```
How does this work? If you do the math, it turns out that `sinh‾¹(.5)` is equal to `ln φ`, so it's a modified version of Binet's formula that rounds down instead of using the `(1/φ)^n` correction term. The `round(` (round to 9 decimal places) is needed to prevent rounding errors.
[Answer]
## K - 12
Calculates the `n` and `n-1` Fibonacci number.
```
{x(|+\)/0 1}
```
Just the `nth` Fibonacci number.
```
{*x(|+\)/0 1}
```
[Answer]
# Julia, 18 bytes
```
n->([1 1;1 0]^n)[]
```
[Answer]
## Java, 55
I can't compete with the conciseness of most languages here, but I can offer a substantially different and possibly much faster (constant time) way to calculate the n-th number:
```
Math.floor(Math.pow((Math.sqrt(5)+1)/2,n)/Math.sqrt(5))
```
`n` is the input (int or long), starting with n=1. It uses [Binet's formula](https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression) and rounds instead of the subtraction.
[Answer]
# [Dodos](https://github.com/DennisMitchell/dodos), 26 bytes
```
	dot F
F
	F dip
	F dip dip
```
[Try it online!](https://tio.run/##S8lPyS/@/58zJb9EwY3LjYvTTSElswBKgfD///8NDQA "Dodos – Try It Online")
### How it works
The function **F** does all the heavy lifting; it is defined recursively as follows.
```
F(n) = ( F(|n - 1|), F(||n - 1| - 1|) )
```
Whenever **n > 1**, we have **|n - 1| = n - 1 < n** and **||n - 1| - 1| = |n - 1 - 1| = n - 2 < n**, so the function returns **( F(n - 1), F(n - 2) )**.
If **n = 0**, then **|n - 1| = 1 > 0**; if **n = 1**, then **||n - 1| - 1| = |0 - 1| = 1 = 1**. In both cases, the attempted recursive calls **F(1)** raise a *Surrender* exception, so **F(0)** returns **0** and **F(1)** returns **1**.
For example, **F(3) = ( F(1), F(2) ) = ( 1, F(0), F(1) ) = ( 1, 0, 1 )**.
Finally, the **main** function is defined as
```
main(n) = sum(F(n))
```
so it adds up all coordinates of the vector returned by **F**.
For example, **main(3) = sum(F(3)) = sum(1, 0, 1) = 2**.
[Answer]
# [TypeScript's type system](https://www.typescriptlang.org), 193 188 186 bytes
```
type L='length'
type T<N,U extends 0[]=[]>=U[L]extends N?U:T<N,[...U,0]>
type S<A,B>=T<A>extends[...infer U,...T<B>]?U[L]:0
type F<N>=N extends 0|1?N:[...T<F<S<N,1>>>,...T<F<S<N,2>>>][L]
```
There's no way to do I/O here, but we can use hovering to view the value (also note that the generated JS is empty):
[![Fibonacci(10)](https://i.stack.imgur.com/fxJ2p.png)](https://i.stack.imgur.com/fxJ2p.png)
Unfortunately, TypeScript has strict recursion limits and on F18 we get a `Type instantiation is excessively deep and possibly infinite.` error:
[![Fibonacci(11)](https://i.stack.imgur.com/33Bqv.png)](https://i.stack.imgur.com/33Bqv.png)
[**Demo on TypeScript Playground**](https://www.typescriptlang.org/play?ts=4.5.4#code/C4TwDgpgBAMgvAcgDYQHYHNgAsEChSRQAqAPAHIA0AqlBAB7BoAmAzlAAwDaAunDwHxwqnGN3qNUrKGQD8VAFylKnAHRqqFdt375w0AMokAghQBCg0kf7jmLVWoCWqAGYQATlA1qVpc9zki3PLsuoQAYuSCZLQMthwAPgCMMmTy9j4kEYaUifx5FN6kWeQUAEx5-NyBuDUowFDOiQDs8lARzfwA3Lh1DYkAHK3t-V1AA)
---
Ungolfed version:
```
type NTuple<N extends number, Tup extends unknown[] = []> =
  Tup['length'] extends N ? Tup : NTuple<N, [...Tup, unknown]>;
type Add<A extends number, B extends number> =
  [...NTuple<A>, ...NTuple<B>]['length'];
type Sub<A extends number, B extends number> =
  NTuple<A> extends [...(infer Tup), ...NTuple<B>] ? Tup['length'] : never;
type Fibonacci<N extends number> =
  N extends 0 | 1 ? N : Add<Fibonacci<Sub<N, 1>>, Fibonacci<Sub<N, 2>>>;
```
[Answer]
## 05AB1E, 7 bytes
Code:
```
1$<FDr+
```
[Try it online!](http://05ab1e.tryitonline.net/#code=MSQ8RkRyKw)
[Answer]
# [Whispers v3](https://github.com/cairdcoinheringaahing/Whispers), 35 bytes
```
> Input
> fₙ
>> 2ᶠ1
>> Output 3
```
[Try it online!](https://tio.run/##K8/ILC5ILSo2@v/fTsEzr6C0hMtOIe1R00wuOzsFo4fbFhiCGP6lJUAZBeP//wE "Whispers v2 – Try It Online") (or don't, as this uses features exclusive to v3)
Simply takes the first \$n\$ elements of the infinite list of Fibonacci numbers.
[Answer]
# [Trianguish](https://github.com/Radvylf/trianguish), ~~152~~ 135 bytes
```
00000000: 0c05 10d8 0201 40d7 0401 4110 4102 a060
00000010: 2c02 b080 2c02 8050 20e4 0211 0710 e209
00000020: 1110 4028 0d00 6020 2902 10c3 0802 a107
00000030: 02a1 0502 8027 0910 290b 1110 403b 0890
00000040: 204d 03d0 503c 0790 602a 1071 02a0 9027
00000050: 0280 b110 8111 0402 70e2 0501 402a 0202
00000060: 9106 1107 0291 0b11 0902 702b 1040 2a10
00000070: 6110 2102 9050 2802 70b1 1071 1104 1102
00000080: 02a1 0502 802c 05   
```
[![Two loop? Too many loop!](https://i.stack.imgur.com/W3v8e.png)](https://i.stack.imgur.com/W3v8e.png)
[Try it online!](https://radvylf.github.io/trianguish/#bRpe5WBWEKfq54fcmvocykcKIEW_rK16GoV0e6r4lucnIdyGjbqJf3c9repFoZbw_neIAf.TpzYLM_49nZVTcuaHAboCGhtT0aTOf5j23UhN0GP.S0Qh2nYlxQT2rGokPwlJ_bsoF6-iPeFkRxL%7EJvlaoxY%7E-Cu47GiimG5Ib0E.HGAeRg69H)
---
Trianguish is my newest language, a cellular automaton sort of thing which uses a triangular grid of "ops" (short for "operators"). It features self-modification, a default max int size of 216, and an interpreter which, in my opinion, is the coolest thing I've ever created (taking over forty hours and 2k SLOC so far).
This program consists of two precisely timed loops, each taking exactly ~~17~~ 11 ticks. The first, in the top right is what actually does the fibonacci part; two S-builders are placed in exactly the right position such that two things occur in exactly the same number of ticks:
1. The left S-builder, `x`, copies its contents to `y`
2. The sum of `x` and `y` is copied to `x`
Precise timing is required, as if either of these occurred with an offset from the other, non-fibonacci numbers would appear in brief pulses, just long enough to desync everything. Another way this could have been done is with T-switches allowing only a single tick pulse from one of the S-builders, which would make precise timing unneeded, but this is more elegant and likely smaller.
The second loop, which is also 11 ticks, is pretty simple. It starts off with a 1-tick pulse of `1n`, and otherwise is `0n`, allowing an n-switch and t-switch to allow the contents of `x` to be outputted once per cycle. Two S-switches are required to make the clock use an odd number of ticks, but otherwise it's just a loop of the correct number of wires.
This program prints infinitely many fibonacci numbers, though if run with Mod 216 on, it will print them, as you might guess, modulo'd by 216 (so don't do that :p).
[Answer]
# [Perl 5](https://www.perl.org/), ~~36~~ ~~35~~ ~~33~~ 32 bytes
*-2 bytes thanks to dingledooper*
```
1x<>~~/^(..?)*$(??{++$i})/;say$i
```
[Try it online!](https://tio.run/##K0gtyjH9n5evUJ5YlJeZl16soJ5aUZBalJmbmleSmGNlVZybWFSSm1iSnKFu/d@wwsaurk4/TkNPz15TS0XD3r5aW1sls1ZT37o4sVIl8/9/I9N/@QUlmfl5xf91fU31DAwNAA "Perl 5 – Try It Online")
This works by using the regex `^(..?)*$` to count [how many distinct partitions](https://en.wikipedia.org/wiki/Fibonacci_number#Symbolic_method) \$n\$ has as a sum of the numbers \$1\$ and \$2\$.
For example, \$5\$ can be represented in the following \$8\$ ways:
```
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
1+2+2
2+1+1+1
2+1+2
2+2+1
```
This tells us that the \$F\_5=8\$.
I had this basic idea on [2014-03-05](https://gist.github.com/Davidebyzero/9090628#gistcomment-1185486) but it didn't occur to me until today to try coding it into a program.
*The following two paragraphs explain the **33 byte** version:*
To count the number of distinct matches `^(..?)*$` can make in a string \$n\$ characters long, we must force Perl's regex engine to backtrack after every time the regex completes a successful match. Expressions like `^(..?)*$.` fail to do what we want, because Perl optimizes away the non-match, not attempting to evaluate the regex even once. But it so happens that it does *not* optimize away an attempt to match a backreference. So we make it try to match `\1`. This will always fail, but the regex engine isn't "smart" enough to know this, so it tries each time. (It's actually possible for a backreference to match after `$` with the multiline flag disabled, if it captured a zero-length substring. But in this particular regex, that can never happen.)
Embedded code is used to count the number of times the regex engine completes a match. This is the `(?{++$i})`, which increments the variable `$i`. We then turn it into a non-match after the code block executes.
To get this down to **32 bytes**, a "postponed" regular subexpression embedded code block is used, `$(??{`...`})` instead of `$(?{`...`})`. This not only executes the code, but then compiles that code's return value as a regex subexpression to be matched. Since the return value of `++$i` is the new value of `$i`, this will cause the match to fail and backtrack, since a decimal number (or any non-empty string) will never match at the end of a string.
This does make the 32 byte version about 7 times slower than the 33 byte version, because it has to recompile a different decimal number as a regex after each failed match (i.e. the same number of times as the Fibonacci number that the program will output). Using `(??{++$i,0})` is almost as fast as `(?{++$i})\1`, as Perl optimizes the case in which the return value has not changed last time. But that would defeat the purpose of using `$(??{`...`})` in the first place, because it would be 1 byte longer instead of 1 byte shorter.
As to the sequence itself – for golf reasons, the program presented above defines \$F\_0=1,\ F\_1=1\$. To define \$F\_0=0,\ F\_1=1\$ we would need an extra byte:
```
1x<>~~/^.(..?)*$(??{++$i})/;say$i
```
[Try it online!](https://tio.run/##K0gtyjH9n5evUJ5YlJeZl16soJ5aUZBalJmbmleSmGNlVZybWFSSm1iSnKFu/d@wwsaurk4/Tk9DT89eU0tFw96@WltbJbNWU9@6OLFSJfP/fyOzf/kFJZn5ecX/dX1N9QwMDQA "Perl 5 – Try It Online")
In the versions below, `(?{++$i})\1` is used for speed (at the golf cost of 1 extra byte), to make running the test suite more convenient.
Here it is as a (reasonably) well-behaved anonymous function (**~~47~~ ~~46~~ 44 bytes**):
```
sub{my$i;1x pop~~/^.(..?)*$(?{--$i})\1/;-$i}
```
[Try it online!](https://tio.run/##VY5NCsIwFISv8pBAErXRIm6M1YuIEDXVB00aktS/UpcewCN6kdq6EFzNN/ANjNO@mLdV0BCix32U0PNFeYv2GCTY8leA6qvTHo22URWLRTDKR6Pi/kTH9FzioYuqMzGiKvCuD1SCuQHJszZUu9rcCMr0Cq50j8dkK5gQaz4kbF0nCcGGb9KJ7KGVfw/y0rN@mk0lwWU2S7sYjXgNmDOCvHYebRxs7KCBLwJBQeH9fAEVjOTJqre4bNoP "Perl 5 – Try It Online") - Displays \$F\_0\$ through \$F\_{31}\$
The above actually runs faster than the standard recursive approach (**39 bytes**):
```
sub f{my$n=pop;$n<2?$n:f($n-2)+f($n-1)}
```
[Try it online!](https://tio.run/##HcpBCsIwEEDRqwwl0IRgsRU3ToMXcaPSyIBOQ5IiErL1AB7Ri8Sa1f@L5yZ/35clTBCip2tE@P/z7Jn4FrCE5QI2PV6CjZsdCh6Ho@CDlYI3g9K1vcoF7ezlyshsUdBodv0arVUCWg2p5DxxbE7cZKgLgroWvu8PtJ2sRGEuPw "Perl 5 – Try It Online") - Displays \$F\_0\$ through \$F\_{31}\$
If that is golfed down using [Xcali's technique](https://codegolf.stackexchange.com/a/182864/17216) it becomes even slower, at **38 bytes**:
```
sub f{"@_"<2?"@_":f("@_"-2)+f("@_"-1)}
```
[Try it online!](https://tio.run/##K0gtyjH9X1qcqlBcUpSZXGKtAGKXJxblZealF1v/Ly5NUkirVnKIV7IxsgdRVmkaIErXSFMbyjLUrP1vnZZfpJFbqZJpa2Ctkmlja2wIpLS1NasVMtM0VDI1qwuKMvNKlGLylGoVwEwFlUw9dYVHbZMU1PU0wEo0FWr/AwA "Perl 5 – Try It Online") - Displays \$F\_0\$ through \$F\_{31}\$
or with the same indexing as my main answer here, **34 bytes**:
```
sub f{"@_"<2||f("@_"-2)+f("@_"-1)}
```
[Try it online!](https://tio.run/##K0gtyjH9X1qcqlBcUpSZXGKtAGKXJxblZealF1v/Ly5NUkirVnKIV7IxqqlJ0wCxdI00taEsQ83a/9Zp@UUauZUqmbYG1iqZNrbGIEpbW7NaITNNQyVTs7qgKDOvRCkmT6lWAcxUUMnUU1d41DZJQV1PA6xEU6H2PwA "Perl 5 – Try It Online") - Displays terms \$0\$ through \$30\$
See [Patience, young "Padovan"](https://codegolf.stackexchange.com/questions/182797/patience-young-padovan/223250#223250) for more variations and comparisons.
# [Perl 5](https://www.perl.org/) `-p`, 28 bytes
```
1x$_~~/^(..?)*$(??{++$\})/}{
```
[Try it online!](https://tio.run/##K0gtyjH9n5evUJ5YlJeZl16soJ5aUZBalJmbmleSmGNlVZybWFSSm1iSnKFu/d@wQiW@rk4/TkNPz15TS0XD3r5aW1slplZTv7b6/38j03/5BSWZ@XnF/3ULAA "Perl 5 – Try It Online")
I've just learned now, 16 months after posting the main answer above, that [Ton Hospel's Sum of combinations with repetition](https://codegolf.stackexchange.com/questions/155938/sum-of-combinations-with-repetition/155955#155955) answer used this same basic technique, predating my post by 3 years.
By combining the tricks used in that answer with those already used here, the program length can be reduced even further.
Perl actually literally wraps the program in a loop using string concatenation when called with `-p`, which I was surprised to learn (I would have implemented it in Perl as an emulated loop). So when this program is wrapped in `while (<>) {` ... `; print $_}` by the `-p` flag, it becomes:
```
while (<>) {1x$_~~/^(..?)*$(??{++$\})/}{; print $_}
```
`while (<>)` implicitly assigns the input from stdin, `<>`, to `$_` (which isn't done when using `<>` normally) at the beginning of each iteration of its loop.
`$\` is the `print` output terminator. By default it is empty, but the above program turns it into an integer by incrementing it on every possible match found by the regex. If only one number \$n\$ is sent to the program via stdin, followed by EOF, then upon exiting the loop `$\` will actually represent the \$n\$th Fibonacci number.
The `while (<>)` exits when it encounters EOF, giving `$_` an empty value. So then `print $_` will print that empty value, followed by the value of `$\`.
As such, it defeats the intended purpose of the `-p` flag, as this program works properly when given a single value followed by EOF; if given multiple newline delimited values, it will output the sum of those Fibonacci numbers after finally being sent EOF (if running the program interactively, this would be done by pressing Ctrl+D at the beginning of a line).
Contrast this with an actually loopable Perl `-p` program at **37 bytes**:
```
1x$_~~/^(..?)*$(?{++$i})\1/;$i%=$_=$i
```
[Try it online!](https://tio.run/##DcvNCoJAFAbQ/fcULibUJPVe/xXxTZIhhhrQUVRIiHz0JrcHzqyWIbNmct5yMdo8V8dV@6wWPSqzyaGu11Eu2yi3x8ttLO2iP47o7oVh51@F13WfIBD660eN0JdW9K3Q1sYgMBKkyJCjQIkKdCKBGJSAUlAGykEFqARV4Bh8HgYn4BSc/aZ505NZ7W0e/g "Perl 5 – Try It Online")
If the same multiline input is given to the 28 byte program, this happens: [Try it online!](https://tio.run/##DctLCoMwFAXQ@V2FA0GtVH1P468DN1JaQpFW0BhioILo0ps6PXB0b0bh1Ox9pVGDei9e0K@6N8PUKyvHtl0maewk7esT3Byt/vM40keYJF108cOu2@LYv@9Rum/OZSAwchQQKFGhRgM6kUAMykEFSIBKUAWqQQ04A5@HwTm4AIvfrO0wq8Vd9fgH "Perl 5 – Try It Online")
Sadly, the `$\` trick can't be used with `say`; it only applies to `print`. The `$,` variable applies to both `print` and `say`, but only comes into play if at least two items are printed, e.g. `say"",""`.
[Answer]
# K - 8 bytes
```
+/[;1;0]
```
## Explanation
It makes use of ngn/k's recurrence builtin.
## How to use
Calculates the `n`th fibonacci number.
To calculate the `n`th put the number at the end of the program:
```
+/[;1;0]40
```
[Answer]
## Ruby, 25 chars
st0le's answer shortened.
```
p 1,a=b=1;loop{p b=a+a=b}
```
[Answer]
### FAC: Functional APL, 4 characters (!!)
Not mine, therefore posted as community wiki. FAC is a dialect of APL that Hai-Chen Tu apparently suggested as his PhD dissertation in 1985. He later wrote an article together with Alan J. Perlis called "[FAC: A Functional APL Language](http://dl.acm.org/citation.cfm?id=1308785)". This dialect of APL uses "lazy arrays" and allow for arrays of infinite length. It defines an operator "iter" (`⌼`) to allow for compact definition of some recursive sequences.
The monadic ("unary") case of `⌼` is basically Haskell's `iterate`, and is defined as `(F⌼) A ≡ A, (F A), (F (F A)), …`. The dyadic ("binary") case is defined somewhat analogously for two variables: `A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …`. Why is this useful? Well, as it turns out this is precisely the kind of recurrence the Fibonacci sequence has. In fact, one of the examples given of it is
```
1+⌼1
```
producing the familiar sequence `1 1 2 3 5 8 …`.
So, there you go, quite possibly the shortest possible Fibonacci implementation in a non-novelty programming language. :D
]