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.


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>

211 Answers 211

up vote 43 down vote accepted

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

  • I wouldn't even think of ^2 as replacement for 0,1. +1 – Konrad Borowski Jan 3 '15 at 20:20
  • 2
    This is no longer valid, you will have to write it as |^2,*+*...*, which is the same number of bytes as 0,1,*+*...*. – Brad Gilbert b2gills Nov 8 '15 at 20:20
  • 5
    Perl is so weird. – Cyoce Jan 29 '16 at 5:45
  • What version of Perl 6 was this answer written in? – CalculatorFeline Jun 6 '17 at 22:03
  • 1
    @CalculatorFeline There was a big change known as GLR (Great List Refactor) which happened shortly before the first official release which was on 2015-12-25. This code would have worked right up until that time. – Brad Gilbert b2gills Mar 12 at 21:30

Brainfuck, 22 strokes

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

Generates the Fibonacci sequence gradually moving across the memory tape.

  • 4
    Beautiful! Litterally beautiful! Or perhaps not... anyways +1 for this :) – Per Hornshøj-Schierbeck Aug 18 '11 at 11:20
  • 2
    This is 3.344 or 4 bytes in compressed brainfuck. (6 ln(22)) / ln(256) – Will Sherwood Feb 2 '16 at 5:12
  • 20
    16 bytes: +[[<+>->+>+<<]>] – primo Sep 12 '16 at 5:19

Haskell, 17 15 14 chars

f=1:scanl(+)1f

Try it online!

  • 4
    Why not cut two spaces to f=0:scanl(+)1 f? – R. Martinho Fernandes Jan 28 '11 at 2:27
  • @Martinho: Edited, thanks. – Anon. Jan 28 '11 at 2:54
  • Wow, that's even shorter than the usual f@(_:x)=0:1:zipWith(+)f x! Have to remember it. – FUZxxl Feb 11 '11 at 21:10
  • 3
    You may even strip another space: f=0:scanl(+)1f. – FUZxxl Feb 12 '11 at 17:38

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);}
  • 6
    Given that n is a uint, n==0 can be shortened to n<1. And the stream can save a few chars by ditching the space after the generic type and declaring x in a wider scope than necessary. In fact, ditch x entirely: n+=c;c=n-c; – Peter Taylor Aug 18 '11 at 11:39
  • 1
    @Peter: Thanks, will edit when I get some time. – Jon Skeet Aug 18 '11 at 12:01
  • Your single value version is as long as my recursive lambda expression answer...nice! – Andrew Gray Apr 9 '13 at 17:29
  • 1
    @wizzwizz4 if I'm not mistaken, if !n works, then so should just n if you flip the conditional. – Cyoce Feb 1 at 4:07
  • 1
    @JonSkeet Aw. And here I was thinking I'd beaten Jon Skeet at C#... :-) – wizzwizz4 Feb 1 at 20:16

GolfScript, 12

Now, just 12 characters!

1.{.@.p+.}do
  • +1 nice work. If you make it shorter than 13 chars, I'll instantly accept your answer (unless someone makes an even shorter answer, of course). :-P – Chris Jester-Young Jan 29 '11 at 23:54
  • 1
    I love a challenge. Done! ;-) – jtjacques Jan 30 '11 at 0:10
  • Nice, you win. At least, until someone makes something even shorter (if that's even possible). :-P – Chris Jester-Young Jan 30 '11 at 0:33
  • 5
    that definition is almost as short as the name 'Fibonacci' itself! +1 – agent-j Jun 18 '12 at 18:21

><> - 15 characters

0:nao1v LF a+@:n:<o
  • Though you can shorten it to 0:nao1v LF a+@:n:<o if you want to. Gives 15 :) In fact, this also makes the output slightly more readable... – tomsmeding Mar 18 '13 at 7:28
  • 4
    13 chars: 01r:nao$:@+$r – randomra Apr 16 '15 at 19:25

J, 10 chars

Using built-in calculation of Taylor series coefficients so maybe little cheaty. Learned it here.

   (%-.-*:)t.

   (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075
  • 2
    @aditsu (q:^-^:p) 6 is 64 729 where p is even. J is probably good for what it does riddles. :) – randomra Mar 7 '13 at 22:54
  • 2
    Even better: (<:^-^:>) 4 is 81 and <:^-^:> 4 is 53.5982. – randomra Mar 7 '13 at 23:21
  • 2
    The emoji demonstrated here is what all J code should strive towards. On a side note, another alternative is +/@:!&i.- using 9 bytes. – miles Jul 31 '16 at 4:26
  • 1
    @miles Very nice! You should post it as it is entirely different from mine. – randomra Jul 31 '16 at 10:21

Hexagony, 18 14 12

Thanks Martin for 6 bytes!

1="/}.!+/M8;

Expanded:

  1 = "
 / } . !
+ / M 8 ;
 . . . .
  . . .

Try it online


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

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

  • You should link to whatever you used to make the pretty pictures, then put the link on esolangs.org/wiki/Hexagony. – mbomb007 Jan 20 '16 at 22:32
  • 1
    @mbomb007 I used gimp to manually create each frame, then uploaded the images to some gif making website. Although, several times during this process I considered making a tool to do it, considering how tedious it was. – FryAmTheEggman Jan 20 '16 at 22:36
  • @FryAmTheEggman Impressive! Make it a challenge. I'm sure somebody will post an answer. :D Even better if you could create a website similar to fish's online interpreter. – mbomb007 Jan 20 '16 at 22:37
  • @mbomb007 That might be a tad ambitious for a challenge on this site, not to mention it would probably suffer a lot from being really broad. I don't think I will post that, but feel free to do it yourself if you think you have a good way of presenting it. Also, I believe Timwi created a C# ide for hexagony, although I've never used it because I haven't bothered with mono. – FryAmTheEggman Jan 20 '16 at 22:44
  • 1
    @mbomb007 The ide lives here, by the way, forgot to link it last time. – FryAmTheEggman Jan 20 '16 at 22:51

Python 2, 34 bytes

Python, using recursion... here comes a StackOverflow!

def f(i,j):print i;f(j,i+j)
f(1,1)

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

Jelly, 3 bytes

+¡1

Try it online!

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.

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.@{.@+}*;
  • 1
    The option is "Calculates, given n, the nth Fibonacci number". So ditch the ~ and you have 11 chars which take n on the stack and leave F_n on the stack. – Peter Taylor Mar 31 '11 at 19:29

Ruby

29 27 25 24 Chars

p a=b=1;loop{b=a+a=p(b)}

Edit: made it an infinite loop. ;)

  • 12
    did anyone notice b=a+a=b is a palindrome? :) – st0le Jan 28 '11 at 11:11
  • 2
    yes st0le did :) – gnibbler Feb 1 '11 at 12:24
  • I know I'm late to the party, but can someone explain how the b=a+a=b part works? Can't seem to wrap my head around it. – Mr. Llama Feb 7 '12 at 17:58
  • 3
    @GigaWatt, Think of it this way, Instructions are executed left to right...so newb=olda+(a=oldb) – st0le Feb 8 '12 at 5:19
  • you can save 2 chars by using loop: p 1,a=b=1;loop{p b=a+a=b} – Patrick Oscity Jun 15 '12 at 13:01

Mathematica, 9 chars

Fibonacci

If built-in functions are not allowed, here's an explicit solution:

Mathematica, 33 32 31 chars

#&@@Nest[{+##,#}&@@#&,{0,1},#]&
  • #&@@Nest[{#+#2,#}&@@#&,{0,1},#]& 32 chars. – chyanog Mar 7 '13 at 3:39
  • 1
    @chyanog 31: #&@@Nest[{+##,#}&@@#&,{0,1},#]& – Mr.Wizard Mar 18 '13 at 6:24
  • @Mr.Wizard 24 chars (26 bytes): Round[GoldenRatio^#/√5]& – JungHwan Min Apr 2 at 4:28
  • or 23 chars (27 bytes): Round[((1+√5)/2)^#/√5]& – JungHwan Min Apr 2 at 4:56

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.

  • 13
    I wouldn't call it obfuscated -- obfuscated code is supposed to be difficult to understand, and as far as dc goes the code here is completely straightforward. – Nabb Feb 6 '11 at 8:17

Prelude, 12 bytes

One of the few challenges where Prelude is actually fairly competitive:

1(v!v)
  ^+^

This requires the Python interpreter 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.

Hexagony, 6 bytes

Non-competing because the language is newer than the question.

1.}=+!

Ungolfed:

  1 .
 } = +
  ! .

It prints the Fibonacci sequence without any separator.

  • 2
    This has the minor problem that it doesn't print any separator between the numbers. This isn't entirely well specified in the challenge though. (And I'm really happy someone is using Hexagony. :)) – Martin Ender Nov 3 '15 at 13:19

K - 12

Calculates the n and n-1 Fibonacci number.

{x(|+\)/0 1}

Just the nth Fibonacci number.

{*x(|+\)/0 1}
  • +1 Not bad! If you could shrink it just one character (and provide me a way to test it), I'll accept your answer. :-) – Chris Jester-Young Apr 4 '11 at 15:47
  • The only way to shrink it would be to replace the function with a call to a known number: n(|+\)/0 1 Test it using this interpreter. – isawdrones Apr 4 '11 at 16:04

TI-BASIC, 11

By legendary TI-BASIC golfer Kenneth Hammond ("Weregoose"), from this site. 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.

Julia, 18 bytes

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

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 and rounds instead of the subtraction.

  • I love this solution – Andreas Mar 27 '16 at 2:27
  • This doesn't seem to work for me, but it's early and I may be missing something! Assuming 0 to be the first number in the sequence, this gives 0, 0, 1, 1, 3, 4, 8, 12, 21, 33 for the first 10 numbers – Shaggy Jun 16 '17 at 9:28
  • @Shaggy Oops! Sorry, I introduced a bug - fixed now. – Hans-Peter Störr Jun 16 '17 at 10:06

Ruby, 25 chars

st0le's answer shortened.

p 1,a=b=1;loop{p b=a+a=b}
  • 6
    Actually you can shorten it even further using a=b=1;loop{p a;b=a+a=b} – Ventero Apr 4 '11 at 12:20
  • 6
    So you st0le his answer? :P – mbomb007 Jan 20 '16 at 22:55

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

  • Oh, I accidentally un-community-wikied your post as part of my (manual) bulk-unwikiing. Oh well. ;-) – Chris Jester-Young Dec 2 '13 at 13:57

05AB1E, 7 bytes

Code:

1$<FDr+

Try it online!

  • 3
    Hi, and welcome to PPCG! Nice first post! – Riker Jul 5 '16 at 13:41

Dodos, 26 bytes

	dot F
F
	F dip
	F dip dip

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.

GolfScript, 13 chars

2,~{..p@+.}do

(My answer from a previous Stack Overflow question.)

Desmos, 61 bytes

Golfed

Click the add slider button for n.

p=.5+.5\sqrt{5}
n=0
f=5^{-.5}\left(p^n-\left(-p\right)^{-n}\right)

The last line is the output.

Ungolfed

Is a function.

\phi =\frac{1+\sqrt{5}}{2}
f_{ibonacci}\left(n\right)=\frac{\phi ^n-\left(-\phi \right)^{-n}}{\sqrt{5}}

R, 40 bytes

Haven't seen a R solution, so:

f=function(n)ifelse(n<3,1,f(n-1)+f(n-2))
  • I know this is an old answer, but you can shorten to 38 bytes – Robert S. Aug 3 at 14:53

Cubix, 10 bytes

Non competing answer because the language is newer than the question.

Cubix is a new 2 dimensional language by @ETHproductions were the code is wrapped onto a cube sized to fit.

;.o.ON/+!)

Try it online

This wraps onto a 2 x 2 cube in the following manner

    ; .
    o .
O N / + ! ) . .
. . . . . . . .
    . .
    . .
  • O output the value of the TOS
  • N push newline onto stack
  • / reflect north
  • o output the character of the TOS
  • ; pop TOS
  • / reflect east after going around the cube
  • + add top 2 values of the stack
  • ! skip next command if TOS is 0
  • ) increment the TOS by 1. This kicks off the sequence essentially.

This is an endless loop that prints the sequence with a newline separator. It take advantage of the fact that most commands don't pop the values from the stack.
If the separator is ignored then this can be done with 5 bytes .O+!)

C#: 38 (40 to ensure non-negative numbers)

Inspired by the beauty of Jon Skeet's C# answer and St0le's answer, another C# solution in only 38 characters:

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

Tested with:

for(int i = 1; i <= 15; i++)
    Console.WriteLine(f(i));

Yay for recursive Func<>! Incorrect when you pass in negative numbers, however - corrected by the 40 character version, which doesn't accept them:

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

Note: as pointed out by @Andrew Gray, this solution doesn't work in Visual Studio, as the compiler rejects the in-line function definition referring to itself. The Mono compiler at http://www.compileonline.com/compile_csharp_online.php, however, runs it just fine. :)

Mono Compilation

Visual Studio: 45

Func<int,int>f=null;f=n=>n>2?f(n-1)+f(n-2):1;
  • looks rather familiar...dunno where I've seen that before... ;) As far as I can tell, though, in C# this is the best way of doing it. However, your way won't work - you have to assign null to your function to use a recursive lambda. As that code stands, it won't compile, with a syntax error 'use of unassigned function f' at the line that your lambda is being defined at. – Andrew Gray Apr 17 '13 at 18:14
  • 1
    Depends on your compiler. :) It does exactly as you say in Visual Studio - but the Mono compiler at compileonline.com/compile_csharp_online.php runs it perfectly as-is. – Troy Alford Apr 17 '13 at 18:45
  • 1
    Didn't know that. I wonder why VS and Mono went two different directions on this one...or, maybe the Mono guys are just smarter. The answer is beyond me. D: – Andrew Gray Apr 17 '13 at 18:49
  • Updated to clearly point out our findings. ;) – Troy Alford Apr 17 '13 at 18:53
  • Does this handle the F(0)=0 case? It's an easy fix that doesn't cost any extra bytes: just exchange :1 for :n – Cyoce Mar 25 '16 at 5:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.