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

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

$+ p,p^ ^ q Try it online! Branch 1 takes a number, prints it, adds it with the number from Branch 2, then puts the result in Branch 2 Branch 2 takes a number, feeds it to the addition with branch 1 then puts the original number (not the sum) in Branch 1. For a better explanation click the link and you'll see it in action. More "readable" version: # Detour, 267 bytes :$v  1v   q   # split into branches

+   # push sum of last 2 fibonacci numbers to branch 2
{

p , p   ^   # print branch 1, merge with branch 3

}

^   q       # push branch 2 into branch 1 for printing and recycling

# 1   2   3

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

# Perl 5, 23 bytes

22 bytes, plus 1 for -nE instead of -e.

say$.-=$b+=$.*=-1;redo Hat tip. # Sesos, 11 bytes (non-competing) Not in-place, linear memory. Hexdump: 0000000: ae8583 ef6bc7 045fe7 b907 ....k.._... Size : 11 byte(s) Try it online! ## Assembler set numin set numout add 1,rwd 1,get ;setup tape jmp fwd 1 jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz rwd 1 sub 1 jmp,sub 1,fwd 1,add 1,rwd 1,jnz fwd 1 jnz fwd 2 put # Java, 71 chars Single number: (Binet formula, considering 1.62 as the golden ratio)) int f(int n){return(Math.pow(1.62,n)-(Math.pow(-1.62,-n))/Math.sqrt(5)} I know this isn't surprisingly short, however Math is beautiful and this formula is even more! # Ruby ## Ungolfed, 60 bytes def fib(prev,nxt) x = prev + nxt puts x fib(nxt,x) end ## Golfed, 33 bytes def f(a,b)x=a+b;puts x;f(b,x)end Pretty simple to call, use f(first, next). • You can still golf it further. Try taking out the unnecessary whitespace. Also, there are some good tips here – James Sep 12 '16 at 5:14 • x=a+b;puts x can become puts x=a+b – Cyoce Dec 11 '16 at 3:26 # Java 8 29 bytes Using Java 8 lambdas. This is a valid statement if there exists a function interface with a method that returns an int and takes an int as a parameter. Also the variable that stores the lambda must be declared as a member (static or non static) of the class it is in so that it can be used recursively. f=n->n<2?0:f.f(n-1)+f.f(n-2); ## Ungolfed: @FunctionalInterface interface F { int f(int n); } public class Main { static F f; public static void main(String[] args) { f=n->n<2?0:f.f(n-1)+f.f(n-2); } } # Prismatic, 113 bytes (can be smaller) right wideness wideness left forward up vertex longness backward right vertex tallness forward down vertex vertex Inspired by Brainfuck, Cubix and Hexagony. # 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. – Ad Hoc 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 – Ad Hoc 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 # Forth, 27 bytes Prints them forever (until it exceeds the maximum integer). : f over . 2dup + recurse ; Try it online Returns the nth Fibonacci number. This assumes I can leave garbage on the stack (the result is still on top), 30 bytes: : f 1 0 rot 0 DO 2dup + LOOP ; Try it online ## Alice, 11 bytes This was a collaborative golfing effort with Sp3000. 1 \ O ,+{.3 Try it online! This prints the Fibonacci sequence indefinitely, starting from 1,1, one integer on a line. Unfortunately, it's horrible in terms of memory, because it leaks one stringified copy of each number in the sequence. The things you do for bytes... ### Explanation 1 Push 1 to initialise the sequence. There's already an implicit zero underneath. \ Reflect to NE. Switch to Ordinal. Immediately reflect off top boundary, move SE. The remainder of the program runs in an infinite loop. At this point of the loop there's the current number F_n of the sequence on top of the stack, and the previous number F_n-1 is below. Stack: [... F_n-1 F_n] . Implicitly convert F_n to a string and duplicate it. [... F_n-1 "F_n" "F_n"] Reflect off bottom boundary, move NE. O Output F_n with a trailing linefeed. [... F_n-1 "F_n"] Reflect off top right corner, move back SW. . Make another copy of F_n. (We don't need this one.) [... F_n-1 "F_n" "F_n"] Reflect off bottom boundary, move NW. \ Reflect to S. Switch to Cardinal. { Turn 90 degrees left, i.e. east. . Implicitly convert F_n to an integer and duplicate it. [... F_n-1 "F_n" F_n F_n] 3 Push 3. [... F_n-1 "F_n" F_n F_n 3] , Pull up the third stack element, which is F_n-1. [... "F_n" F_n F_n F_n-1] + Add F_n and F_n-1. [... "F_n" F_n F_n+1] { Turn 90 degrees left, i.e. north. \ Reflect to SE. Switch to Ordinal. After this point, the loop repeats. # Taxi, 864 bytes 1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:W 1 L 2 R 1 L 1 L 2 L.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Cyclone.Go to Sunny Skies Park:W 1 R.[a]Go to Cyclone:N 1 L.Pickup a passenger going to The Babelfishery.Pickup a passenger going to Addition Alley.Go to Fueler Up:N 2 R, 2 R.Go to The Babelfishery:S.Pickup a passenger going to Post Office.Go to Post Office:N 1 L 1 R.Go to Sunny Skies Park:S 1 R 1 L 1 R.Pickup a passenger going to Cyclone.Go to Cyclone:N 1 L.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:N 2 R 1 R.Pickup a passenger going to Sunny Skies Park."," is waiting at Writer's Depot.Go to Writer's Depot:N 1 L 1 L.Pickup a passenger going to Post Office.Go to Sunny Skies Park:N 2 R.Switch to plan "a". Try it online! Ungolfed: 1 is waiting at Starchild Numerology. 1 is waiting at Starchild Numerology. Go to Starchild Numerology: west 1st left 2nd right 1st left 1st left 2nd left. Pickup a passenger going to Sunny Skies Park. Pickup a passenger going to Cyclone. Go to Sunny Skies Park: west 1st right. [a] Go to Cyclone: north 1st left. Pickup a passenger going to The Babelfishery. Pickup a passenger going to Addition Alley. Go to Fueler Up: north 2nd R, 2nd right. Go to The Babelfishery: south. Pickup a passenger going to Post Office. Go to Post Office: north 1st left 1st right. Go to Sunny Skies Park: south 1st right 1st left 1st right. Pickup a passenger going to Cyclone. Go to Cyclone: north 1st left. Pickup a passenger going to Addition Alley. Pickup a passenger going to Cyclone. Go to Addition Alley: north 2nd right 1st right. Pickup a passenger going to Sunny Skies Park. "," is waiting at Writer's Depot. Go to Writer's Depot: north 1st left 1st left. Pickup a passenger going to Post Office. Go to Sunny Skies Park: north 2nd right. Switch to plan "a". # Braingolf, 23 bytes 1!_# @.!_[# @!+!_<1+>]; Try it online! • 17 bytes – Skidsdev Jun 16 '17 at 9:20 • 14 bytes – Skidsdev Jun 16 '17 at 9:23 • 8 bytes for output the nth number – Skidsdev Jun 16 '17 at 9:35 # Joy, 45 bytes DEFINE f ==[2<][][[1 - f][2 - f]cleave+]ifte. Try it online! Zero-indexed. Example usage: 6 f yields 8. [2<] ifte . if the top stack element is less than two [] . then do nothing [ cleave ] . else duplicate the element and apply two functions + . and sum the results [1 - f][2 - f] . where the functions compute the two previous Fibonacci numbers Alternative (same byte count): DEFINE f ==[2<][][dup 1 - f swap 2 - f+]ifte. # cQuents, 6 bytes =1:z+y Try it online! This works both with and without input - it prints the sequence without input, and the nth item (1-indexed) with input n. For 0, 1, 1, ... version, 8 bytes: =0,1:z+y Try it online! # Explanation =1 Set first item in sequence to 1 : Mode: Sequence 1 (prints sequence with no input, or nth item with input n z+y Each term equals the previous two terms added together (defaults to 0) I really, really like the way this language is going :) • Note current version uses Z and Y instead of z and y – Stephen Feb 1 '19 at 4:54 # ReRegex, 50 bytes. (0+),(0+):0/$1,$2,$1$2:/.*?(0+),0+:$/$1/0,0:#input 0 indexed. Takes input and gives output via Unary. Try it online! ## About the Program ReRegex was designed to be much like an advanced version of ///. It offers the same very basic concept of repeatedly doing string match and replace operations. However, that's where the similarities end. ReRegex instead uses a list of match and replace operations, separated by /s, to perform in a loop, and the original string to effect. The Regexes will continue being performed on the original string until a constant state is achieved, at which point the program will dump the string to STDOUT. This program in particular is just 2 regular expressions and then the input with some default values. (0+),(0+):0 ->$1,$2,$1$2: .*?(0+),0+:$ -> $1 And the input is formatted with; 0,0:#input ReRegex defaultly replaces #input with whatever is passed to the program on STDIN. For an example, let's say 00000 is passed to STDIN. First, the "Memory" looks like this: 0,0:00000 In the first loop, the regex (0+),(0+):0 is matched, the replace then creates the next itteration of the fibonnachi sequence. 0,0,00:0000 And in doing so, it also pops one of the 0's off, which is why :0 is at the tail end of the match, but not the replace. This then happens 4 more times in a row. 0,0,00,000,00000,00000000,0000000000000: Now that first regex doesn't match, as there's no more :0 at the end, so we're almost at a stable end point. Now that there's nothing after :, .*?(0+),0+:$ matches, and all it does is clear all data but the second last group of 0s.

00000000

Now, nothing else matches, so it's outputted.