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

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;
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
var id = +a.share_link.match(/\d+/);
});
if (!data.has_more) more_answers = false;
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>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

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 {
}
<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">
<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>

# C#

### Generated as a stream (65 chars):

IEnumerable<int>F(){for(int c=1,s=1;;){s+=c=s-c;yield return c;}}

Could be reduced to 61 characters using non-generic IEnumerable. Of course, if you include the required System.Collections.Generic, then it's a few more characters.

Mathematica,26 chars

If[#>1,#0[#-1]+#0[#-2],#]&
• Damn, and I just thought I had come up with a new shortest Fibonacci implementation in Mathematica. +1 :) – Martin Ender Jan 30 '15 at 21:08
• What does the trailing & do? – Cyoce Oct 14 '16 at 0:55
• @Cyoce making it a function, instead of an expression – Keyu Gan Feb 1 '18 at 0:40

## F# - 42 chars

Seq.unfold(fun(a,b)->Some(a,(b,a+b)))(0,1)
• Nice, I didn't know about Seq.unfold! =) – Roujo Feb 8 '16 at 20:32

# PowerShell: 42 or 75

Find nth Fibonacci number - 42

A spin-off of Joey's answer, this will take user input and output the nth Fibonacci number. This retains some weaknesses also inherent to Joey's original code:

• Technically off by 1, since it starts the Fibonacci sequence at 1,1 instead of the more proper 0,1.
• Only valid for Fibonacci numbers which will fit into int32, because this is PowerShell's default type for integers.
• Example: Due to the int32 limitation, the highest input that will return a valid report is 46 (1,836,311,903) and this is technically the 47th Fibonacci number since zero was skipped.

Golfed:

($b=1)..(read-host)|%{$a,$b=$b,($a+$b)};$a Un-Golfed & Commented: # Feed integers, from 1 to a user-input number, into a ForEach-Object loop. # Initialize$b while we're at it.
($b=1)..(read-host)|%{ # Using multiple variable assignment... # ...current$b is put into new $a, and... # ...sum of current$b and current $a are put into new$b.
$a,$b=$b,($a+$b) }; # When loop exits, output$a.
$a # Variable cleanup, not included in golfed code. rv a,b List Fibonacci numbers - 75 Another derivative of Joey's answer, but with some improvements: • Zero is included in the output, as it should be according to OEIS. • Goes up to the maximum Fibonacci number that can be handled as uint64 instead of the default int32. (Highest Fibonacci number in uint64 is 12,200,160,415,121,876,738.) • Output stops once the maximum value is reached, instead of looping through 'Infinity' or continuously throwing errors. Golfed: for($a,$b=0,1;$a+$b-le[uint64]::MaxValue){$a;$a,$b=$b,[uint64]($a+$b)}$a;$b Un-Golfed & Commented: # Start Fibonacci loop. for ( # Begin with$a and $b at zero and one.$a,$b=0,1; # Continue so long as the sum fits in uint64.$a+$b-le[uint64]::MaxValue ) { # Output current$a.
$a; # Using multiple variable assignment... # ...current$b becomes new $a, and... # ...sum of current$b and current $a is forced to uint64 and stored in new$b.
$a,$b=$b,[uint64]($a+$b) } # Output$a and $b one more time.$a;$b # Variable cleanup - not included in golfed code. rv a,b • One thing that bugs me a little in PowerShell: Read-Host always reads interactively and won't pick up things you pipe into the script (or process), whereas$input (which is what I tend to use) only picks up piped input (for obvious reasons; that's how it's defined) but cannot be used interactively. Which means that you can write a PowerShell script that either works interactively or one that works with piped input, but not both at the same time (at least not for golfing). – Joey Nov 28 '13 at 20:21
• Yeah, and I personally prefer my scripts to be interactive whether the challenge calls for it or not. Wait... Did you just golf the un-golfed code? And not just any part of it, but particularly the bit that's not at all in the golfed code? – Iszi Nov 28 '13 at 22:57
• I merely optimized it, since Remove-Variable takes a string[]. There is no need to have two calls ;-) – Joey Nov 29 '13 at 6:13
• I meant to say I found it amusing that of all the code to be optimized, you had to go and fix the bit that wasn't even part of the golfed solution. It's like you had an OCD moment or something. – Iszi Nov 29 '13 at 7:25
• Sometimes I do ;-). I don't see anything that makes the golfed code smaller either. For an algorithm this simple there aren't many options and range|% is often the shortest (but also the slowest) way. – Joey Nov 29 '13 at 7:27

# JAGL V1.0 - 13 / 11

1d{cdc+dcPd}u

Infinite Fibonacci sequence. Or, if not required to print:

11 bytes

1d{cdc+cd}u

# Octave, 26 chars

f=@(n)([1 0]*[1 1;1 0]^n)(2)

Basically, a copy of my solution from Calculating (3 + sqrt(5))^n exactly.

, so

It's a disaster to do unnecessary* loops in Octave/Matlab. It's neither elegant, nor fast, let alone golfy.

*All loops that can be vectorized are unnecessary :).

• I don't think you need the [1 0]. Picking the second item out of the matrix will give you the right number anyway. – Andrew Piliser Apr 16 '15 at 21:37
• Thank you for notice, f=@(n)([1 1;1 0]^n)(3) is six characters shorter indeed (Octave enumerates items in matrix top-down and then left-right when indexing with a single number, so the value at first row, second index is at index 3). – pawel.boczarski Apr 16 '15 at 22:22

# Ruby, 28 bytes

->f{loop{f<<p(f[-1]+f[-2])}}

Usage:

->f{loop{f<<p(f[-1]+f[-2])}}[[-1,1]]

# 𝔼𝕊𝕄𝕚𝕟, 3 chars / 6 bytes (noncompetitive)

Мȫï

Try it here (Firefox only).

More builtins!

math.js + numbers.js = hella functions

# PARI/GP, 9 bytes

fibonacci

Alternate solution (21 bytes), for those disliking the built-in:

n->([1,1;1,0]^n)[1,2]

Alternate alternate solution (21 bytes):

I also posted all three solutions (in ungolfed form) to Rosetta Code's Fibonacci page.

# Reng v.2.1, 18 bytes

(Noncompeting, postdates question)

11{:nAo}#xxx:)+x5h

11 initializes the stack with 2 1s. {:nAo}#x sets the command x to mean "duplicate and output as number" (:n) then "output a newline" (Ao, A = 10). Then, xx prints the initial 2 1s. : duplicates the TOS and ) rotates the stack, so it becomes b a b. + adds the two figures, making it b (a+b). x prints and leaves this new result on the stack. 5h jumps back 5 spaces, and the loop continues.

# Fuzzy Octo Guacamole, 11 bytes

01(!aZrZo;)

This takes the infinite route.

Explanation:

01 pushes 0 and then 1 to the stack.

( starts a infinite loop.

! sets the register, saving the value on the top of the stack and storing it. It doesn't pop though.

a adds the 2 values.

ZrZ reverses the stack, pushes the register contents, and reverses again. This pushes the stored number to the bottom of the stack.

o; peeks and prints.

) ends the infinite loop.

Then the whole things starts again from the (.

As a a side note, this is quite fast to hit the max long size possible in Python. The last number it prints is 12200160415121876738, and it repeats that forever.

# R, 33 bytes

CAUTION: This attempts to print the whole Fibonacci sequence. It relies on an overflow of the sequence to stop. On my computer that is around 10^308, so it runs and dies pretty quickly -- throwing an error.

a=1;b=0;while(print(b<-a+b))a=b-a

Pretty simple. Initialize a and b. Then a while loop which adds them to find the next number and print it. Turns out -- two steps after the first numeric overflow, when both a and b are Inf we get NaN or not a number. This gets printed by the print command. But the value it returns is not evaluable by while as true or false (unlike numbers, NaN doesn't have a default logical interpretation), and so the loop throws an error and stops.

Obviously, this pleasant feature relies on about 5 defaults to stop what is otherwise an infinite loop. Works in R 3.2.2

# Cylon (Non-Competing), 12 bytes

The language is in development, Im just putting this up here.

1:øÌ[:ì+Á])r

An explanation:

1    ;pushes a 1 to the stack
:    ;duplicates the top of the stack
ø    ;reads a number from stdin, pushing it to the stack
Ì    ;non-pushing loop, doesn't push counter to the stack, but deletes it
[    ;start of function, to be pushed to the stack
:  ;duplicate top of stack
ì  ;rotate the stack, moving the copy to the back
+  ;replaces top two objects on the stack with their sum
Á  ;push the result to the shadowing stack (non-consuming)
]    ;end of function
)    ;switch to shadowed stack
r    ;standard library call, reverses a stack
;stack implicitly printed

# Javascript, 28 Characters

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

Try it here!

• Welcome to PPCG! How about n<3? And do you really need the parentheses around the inequality? You can probably also omit the semicolon. – Martin Ender Mar 25 '17 at 19:43

# OIL, 46 bytes

This program writes an infinite unstoppable stream of fibonacci numbers. It is mostly copied from the standard library but fit to the requirements and golfed.

14
17
17
14
swap
17
17
4
17

11
6
0
0
1
• Welcome to the site! This is a cool answer, I've never heard of the language before. :) – DJMcMayhem May 4 '17 at 17:29

# Python 2, 30 bytes

f=lambda n:n<3or f(n-2)+f(n-1)

Try it online!

One catch: this outputs True instead of 1. This is allowed by this meta consensus.

# Gaia, 6 bytes

0₁@+₌ₓ

I might make a built-in for this in the future, but built-ins are boring anyway.

### Explanation

0₁      Push 0 and 1
@     Push an input
+₌ₓ  Add the top two stack elements, without popping them, (input) times
Implicitly print the top stack element.

# Emojicode, 100 bytes

🐖🔢➡️🚂🍇🍊◀️🐕2🍇🍎🐕🍉🍓🍇🍎➕🔢➖🐕1🔢➖🐕2🍉🍉

Try it online!

# Python 2, 49 40 chars

a,b=0,1
exec"a,b=b,b+a;"*input()
print b

### Function form, 44 chars

def f(n):a,b=0,1;exec"a,b=b,b+a;"*n;return b

My take on this challenge. Didn't find this kind of an answer yet. I hope it's a valid one.

Print's n:th Fibonacci number. Functions by multiplying the string inside exec n times and then executing it as Python.

Edit: input() instead of int(raw_input())

• If I'm not mistaken, you don't need to the () around exec in Python 2. – Stephen Jul 21 '17 at 14:07
• @StepHen That seems to be true, thanks, down by 2 chars – SydB Jul 21 '17 at 14:11
• Oh, I almost forgot: this would be considered a snippet because it preassumes the value of n. Generally you must write either a full program that gets input, or a function. So, you would have to replace n with input(). See this meta post for more information. – Stephen Jul 21 '17 at 14:15

# Klein, 2322 21 + 3 = 24 bytes (non-competing)

Run with the 000 topology

(1)\((@
):?\1-+(:(+)$## Explanation When the program starts it executes (1) which will put a 1 under the input. It then deflects into the main loop. The main loop is on the second line. It starts with the \ character. Unwrapped it looks like: \1-+(:(+)$):?

This will redirect our pointer if the counter is zero or perform one iteration of the fibonacci sequence otherwise.

Once the counter reaches zero we are deflected to the code ((@, this will hide the top two values (the counter and one of the fibonacci numbers) and terminate the program.

## Piet, 17 codels

Not sure how to count this one. There are 17 pixels within the code that count as instructions/control flow modifiers (18 if you count the required NOP to get the color back to the correct cycle for the loop).

Shown here at 20 pixels per codel:

Explanation in pseudocode:

push 1
push 1
push 1
push 1
out (number)
out (number)
START OF INFINITE LOOP
duplicate
push 3
push 1
roll ; the last three instructions amount to "rotate the top to the third spot once"
duplicate
out (number)
END OF INFINITE LOOP

This outputs the Fibonacci sequence (starting with 1,1) without delimiters.

Actual image (way too small to see clearly):

• Oh, didn't know there was a convention for this. Was unsure. Will change now. – Josiah Winslow Sep 13 '17 at 11:29

# C, 64 bytes

a,x,y,z=1;main(){for(;;){a=y;y=z;z=a;x+=y;y=x;printf("%d ",x);}}

Try it online! Uses the same method as my Implicit answer.

• – Jonathan Frech Aug 19 '18 at 4:01

# Haskell, 30 bytes (was 33)

f=0:1:[f!!n+f!!(n+1)|n<-[0..]]

Try it online!

• You should add a TIO link and some sample cases – Muhammad Salman Aug 9 '18 at 19:32
• @MuhammadSalman They do not have to add a link. I think "should" is a bit too forceful. – Jonathan Frech Aug 9 '18 at 19:52
• Ok I added the TIO link, this is my first time posting – mrFoobles Aug 9 '18 at 22:04
• @mrFoobles For demonstration purposes, I think main=print f would be more impressive as it shows the magnitude of infinite lists. – Jonathan Frech Aug 9 '18 at 22:19
• @JonathanFrech yeah, should have been you could add and not should add – Muhammad Salman Aug 10 '18 at 10:28

# 05AB1E, 2 bytes

Åf

Try it online!

1-indexed. Built-in.

# 05AB1E, 2 bytes

λ+

Try it online!

0-index. Non-built-in. As far as I know, this is the first answer using the major 05AB1E rewrite, and uses its newest addition, λ...}, recursive list generation.

### How it works

λ+ – Full program.
λ  – Starting from 1, recursively apply a function and collect the results
in an infinite list.

# Alchemist, 68 bytes

y+_->y+a+b
y+0_->z
z+a->z+_
z+0a->x
x+b->x+a
x+0b->y+Out_a+Out_" "!y

Try it online!

Outputs the 1-based sequence infinitely, If you want 0-based (i.e. 0 1 1 2 3 5...), you can change the trailing y to either x or z.

### Explanation:

!y              # Initialise the program with the y flag alongside the default _

y+_->y+a+b      # Convert all _ atoms to a and b atoms
y+0_->z         # Once we're out of _ atoms, change to the z flag

z+a->z+_        # Convert the a atoms back to _ atoms
z+0a->x         # Switch to the x flag

x+b->x+a        # Convert all b atoms to a atoms
x+0b->y         # Once we're out, change to y flag
+Out_a   # Print the number of a atoms
+Out_" " # And a separator

If it makes you feel better, here's a more pseudo-codey version:

_=1
while true:
a=a+_
b=_
_=a
a=b
print a

# Java, 100 characters and just two variables

There was one before with 55 characters, but it used a variable without declaring it and had no output. This one has both and (the actual logic) is shorter. And as a little bonus it looks absolutly horrific code-style-wise and depends on compiler quirks, yay!

public class A{public static void main(String[]a){for(int a,b=a=1;;System.out.println(b=a+(a=b)));}}

The special features I used are:

• Declaring multiple variables at once: int a,b;
• Initializing multiple variables at once and in the declaration, needs a second a: b=a=1;
• Everything is done in the for head, the body is empty: for(...);
The first and third block of for are intended for variable initialization and variable incrementation, but they can hold any commands.
• The whole logic is inside the output: System.out.println(b=a+(a=b))
• Just two variables without recursion! This is done by using the way the compiler works: The assignment to b first reads the value of a, then it evaluates the right side of the +, where it reads the value of b and writes it into a, but the left side of the + still has the old value of a that gets added to the value of b after assigning the value of b to a. Then that sum gets written to b while a already holds the old value of b.
I was lucky that the compiler works this way, because it could also have first evaluated the expression in the brackets, like for example C does, then it just lists all powers of 2 instead of the Fibonacchi numbers.

In a dream programming language this would just be: b=a+(a=b

• Dammit, referring to this answer just helped me in actually useful code, but I can't upvote it! :D – Fabian Röling May 27 at 21:56

## Scala, 52 chars:

def f(a:Int,b:Int):Int={println(a);f(b,a+b)};f(0,1)

CHIP 8

Not so short but displays the fibonacci sequence on screen:

00E06600690060006101221E3900120E8200801081206F00810489F0120A6500830064F083428336833683368336F32900E0D56575088300640F8342F329D56500EE

without displaying on screen:

00E06000610182008010812081041206

Clojure: 38 chars

(def f(lazy-cat[0 1](map +(rest f)f)))

run with:

f

# Javascript - 48 chars

for(i=1;i<n;i++){f[i]=f[i-1]+(f[i-2]?f[i-2]:0);}

Clean and simple... probably not a shortness winner :D

Here is the full implementation:

function a(n) {
var i;
var f = new Array();
f[0]=1;

for(i=1;i<n;i++){f[i]=f[i-1]+(f[i-2]?f[i-2]:0);}

console.log(f);
}