Challenge: Write the recursive Fibonacci algorithm in a different language.

Douglas R Andreani on August 21, 2018

Hellow DEV community, how are you? Can we challenge ourselves in this fun "game"? Let's see how many languages we can enumerate by writing the ... [Read Full]
markdown guide

I'll continue with javascript.

const fibonacci = (n, i=0, curr=1, prev=0) =>
    (i >= n ? curr : fibonacci(n, i + 1, curr + prev, curr))

(Look mum, with a single expression function!)


To be absolutely pedantic, this code is valid and will work with large numbers because it is written in EcmaScript 6. Part of the ES6 standard is for the language interpreter to implement tail call optimization (TCO). EcmaScript is a language defined by a standard, not by an implementation.

Now, at present, barely any interpreters implement TCO - here's a fun comparison table to see which do or don't. This makes me sad, but there we are.

But, as I say, the function above will work just fine according to the language standard. Whether this code blows the call stack of your interpreter is dependent on whether your interpreter implements the full ES6 standard. Which it probably doesn't.

To put it strongly, complaining that this code doesn't run on an JS interpreter without TCO is like complaining that it can't run by a Ruby interpreter. The fault is with the interpreter, not the code.


I like this! Don't think you need the outer parens though :D


Should work without, I'm just used to wrapping ternary expressions between them for some reason and I find it weird without :)

VM172:1 Uncaught RangeError: Maximum call stack size exceeded

man, just sit down and relax. there is no point for all this harassement.

Since when pointing out the solution does not work is considered a harassment?

Does not “challenge” implies “produce working answers,” not just “spit out several lines of code that do not work”? Am I missing something?

If you think it's important enough for a code challenge to have a Javascript implementation that returns Infinity instead of blowing the stack for large values, be my guest and suggest an alternative implementation.

Just posting the console output of calling my function with an arbitrarily long value seems rather pointless. I agree my solution is not perfect but I'd appreciate a better solution more than an error message.

How is that Infinity? Also, I have posted two solutions myself, both working for arbitrarily large values. Just scroll the page to see them.

I have no idea of how it should be handled in javascript, probably one should read some paper on tail-call optimization in ECMAScript, or something.

Please do not feed this troll.

He picked fib(10000) because it blows Int64 and now he's trying to victoriously convince everyone their programming language of choice is crap.

The same as if I would say I can compute and save a file containing Pi to 1e+13 numbers and don't tell anyone I have 12TB NAS storage attached...

Aleksei, if you try to work with very large numbers in Javascript, at some point (before the 10000th element in the fibonacci series) it just returns Infinity because it can't deal with them.

if you try to work with very large numbers in Javascript, at some point (before the 10000th element in the fibonacci series) it just returns Infinity

The issue was not an Infinity but stack overflow in the first place. If I were to solve the problem in Javascript, I would need to maintain that number myself, like storing a string and adding up new numbers manually. Language limitations are the worst excuse for the developer, aren’t they?

He picked fib(10000) because it blows Int64 and now he's trying to victoriously convince everyone their programming language of choice is crap.

You have no idea why I picked up 10000, your guess is plain wrong and your wild suggestion about I am “trying to victoriously convince” anybody in anything is ridiculous and outrageous at the same time.

Language limitations are the worst excuse for the developer, aren’t they?

It's also rather convenient to claim that other people's proposal is incorrect because they have to implement things that your language of choice gives you for free (or, in the case of Ruby, you need to enable a runtime option; still beats Javascript's strategy of not having it at all).

According to you I should not only hack tail-call optimisation into Javascript somehow (most current runtimes don't do any kind of tail-call optimisation, ever), but roll my own custom system to handle arbitrarily large numbers. I don't really think this was the point of the challenge.

Also, let's keep in mind that my solution blows when the stack isn't big enough to keep track of all the function calls, and yours blow when the number is too large to be kept in memory. So, while in practice my solution blows much, much earlier than yours, both are, technically, incorrect if the definition of correct is that it works for all natural numbers, and they are both incorrect for the same reason: computer limitations apply.

So, while in practice my solution blows much, much earlier than yours, both are, technically, incorrect if the definition of correct is that it works for all natural numbers, and they are both incorrect for the same reason: computer limitations apply.

The word you are looking for is "totality". Function is total if it returns a value for each input in the domain

According to you I should [...]

Please don’t put words in my mouth. I never said anything about what you should do. I said how I was to approach the issue.

Thinking about all limitations and pitfalls of the solution before starting to implement it is a must. That has nothing to do with the language of choice.

I once saw the currency rate implemented with float type, that cost the company nearly $100K when it came to rounding big numbers. Can we consider the solution using floats working? Well, we can and the developer probably could. The company couldn’t.

That’s my main point: unless one knows that the code has limitations and unless these limitations are described on the very top of this code in all caps, the code can’t be considered to be robust. As I am paid for producing code, not robust equals to not working for me.


No worries @avalander . You all did right, it is just JS doesn't support TCO there were some attempts (as far as I remember it is hold back by Microsoft member or committee or something like that). There is still way around - you can use trampoline

const trampoline = (fn) => {
  let newFn = eval(fn.toString().replace(new RegExp(fn.name + '\\(([^\\)]*)\\)'), '[$1]'))
  return function() {
    let result = newFn.apply(null, arguments)
    while (result instanceof Array) result = newFn.apply(null, result)
    return result

const _fibonacciIter = (n, i, curr, prev) =>
    (i >= n ? curr : _fibonacciIter(n, i + 1, curr + prev, curr));

const fibonacciIter = trampoline(_fibonacciIter);

const fibonacci = n => fibonacciIter(n, 0, 1, 0);

I doubt you would want to use this in production, but just to make a point.

TCO - stands for tail call optimisation, to prevent Maximum call stack error
Trampoline is the way how some compilers implement TCO, they convert recursion to a loop

UPD: read about TCO status in Chrome here stackoverflow.com/questions/427881...

Wow, that's great, I didn't know this trick, thank you!


I haven't seen a SQL implementation yet, so here's one:

with recursive fib(a, b) as
    (select 1 as a, 0 as b


     select a + b as a, a as b from fib)

select a from fib limit 10;

Here's interesting one for SQL Server with maximum value before arithmetic overflow due to data type limit:


SET @MAX = 1474

    FLOOR(POWER(( 1 + SQRT(5) ) / 2.0, number) / SQRT(5) + 0.5) AS Fib
FROM master..spt_values
) AS s

Execution plan


Here it is in Oracle SQL:

      1 i, 0 SPIRAL, cast(null as number) PREV 
   union all
      f1.i + 1 i, f1.SPIRAL + nvl(f1.PREV,1) SPIRAL, f1.SPIRAL PREV
       FIBONACCI f1
   f1.i < 605

select SPIRAL from FIBONACCI order by i;

The limit of 605 is the limit before numeric overflow.


👏👏 I never thought you could do that with SQL!


Fuck yes SQL!

I feel like every time someone responds to one of these with a SQL implementation that a) my heart grows a few sizes and b) they earn extra special bonus points in my head because hell yeah.


(nonironic gold star, fwiw)


I'll follow up in C# (and LINQ):

  Enumerable.Range(1, 10)
    new { Current = 1, Prev = 1 }, (x, index) => new { 
      Current = x.Prev + x.Current, Prev = x.Current }

(Look ma', single expression lambda without recursion!)


Imaginative, I like it (even if it's not recursive :P)!


I lied a bit. The recursion is there, hidden in the Aggregate function. It's the framework abstraction that masks it.

Otherwise it wouldn't qualify as an answer to OP challenge, or would it? ;)

I know nothing about C#, but I thought that the Aggregate function was somehow invoking an anonymous function here that given current and previous values returns the next element. If that's the case, and it's a function calling another function multiple times instead of the function invoking itself, can we still call it recursion?

The Aggregate function is member of the Enumerable type and applies an anonymous accumulator function looping all elements in that "array/set". Hard to tell if we can treat it as a recursion. I would have to look at the stack if there are pointers left to the originating caller.

Fibonacci's sequence is strictly sequential so it works well but for more parallel calculations, like SUM, AVG, MAX, MIN accumulator functions you can do:

var result = Enumerable.Range(1,100000)
  .Aggregate(0, (sum, i) => { sum += i } );

And it will multithread across many OS threads to achieve the best efficiency.

Edit: This is however not plain C# .Net anymore but LINQ ;)


I doubt it’s able to calculate 10000’s Fibonacci number.

> #reset
Resetting execution engine.
Loading context from 'CSharpInteractive.rsp'.
> var start = DateTime.Now;
. Console.WriteLine(
.   Enumerable.Range(1, 10000)
.   .Skip(2)
.   .Aggregate(
.     new { Current = 1, Prev = 1 }, (x, index) => new {
.         Current = x.Prev + x.Current,
.         Prev = x.Current
.     }
.   ).Current
. );
. Console.WriteLine(DateTime.Now - start);

Eh. 10000’s Fibonacci number has a length of 2090 characters. Here is the value:


I see what you did there. Trying to troll languages that you think may not have Int128 support :D. Nice try!

using System;
using System.Linq;
using System.Numerics;

namespace ConsoleApp1
    class Program
        static void Main(string[] args)
            var start = DateTime.Now;
              Enumerable.Range(1, 10000)
                new { Current = (BigInteger)1, Prev = (BigInteger)1 }, (x, index) => new {
                    Current = x.Prev + x.Current,
                    Prev = x.Current
            Console.WriteLine(DateTime.Now - start);

I didn’t try to troll anything, neither have I any clue about Int128 support in C#; I just pointed out that the previous one was incorrect :)

You said you doubt it can compute fib(10000). What were your doubts based on if you have no clue about C#? Plain trolling.

You have posted the snippet that was not robust enough and I pointed out to that.

Once again, for clarity: the code you have posted in your first attempt was buggy and it could not calculate fibonacci numbers for any desired input.

Calling me troll or whatever won’t make this code working. Your second attempt was successful, congratulations. Not that bad, to solve the fibonacci problem from the second attempt.

I'm just letting everyone (else) know I'm not reacting to his childish unsuccessfull trolling attempts anymore... I'm not his mother to raise him to his adulthood.

I know my shit, anyone who writes C# can see it as well. I will now just silently laugh...


Since I doubt anybody else is going to do it, here is an implementation in Scheme

(define (fib n)
    (define (fib-iter a b count)
        (if (= count n)
            (fib-iter (+ a b) a (+ count 1))))
    (fib-iter 1 0 0))

Tested for values of n up to 10001.


Tested for values of n up to 10001.

It’s tail-call optimized, of course, it’ll work for any arbitrarily huge input.


Lord, we got it, you're the best fibonnaci solver out there. Congratulations on this!


I did this some time ago in Rust.

My first approach (the naive one) is very similar to @rapidnerd 's (George Marr's) solution in R and @andreanidouglas ' (Douglas R Andreani's) solution in Python:

fn fib(n: u64) -> u64 {
  match n {
    0 => 0,
    1 => 1,
    _ => fib(n-1) + fib(n-2),

I realized that this solution quickly exceeded in execution time for n > 40, so I optimized it using a mathematical theorem:

Given that n and p are integers, and that n = 2p + 1, i. e. n is odd, the n-th fibonacci number is then

fib(n) = fib(p + (p+1)) = fib(p)² + fib(p+1)²

This means, we can break down numbers with odd indices into to numbers with about the half of the index – and do this again and again and again. This dramatically reduces execution time:

fn fib_fast(n: u64) -> u64 {
  match n {
    0 => 0,
    1 => 1,

    // even
    _ if n % 2 == 0 => fib_fast(n-1) + fib_fast(n-2),

    // odd
    _ => {
      let a = (n-1)/2;
      let b = n-a;
      let fib_a = fib_fast(a);
      let fib_b = fib_fast(b);
      return fib_a*fib_a + fib_b*fib_b;

Inspired by @avalander 's answer, I also added this even faster algorithm:

fn fib_super_fast(n: u64, i: u64, curr: u64, prev: u64) -> u64 {
  if i >= n {
    return curr;

  return fib_super_fast(n, i + 1, curr + prev, curr);

fib_fast and fib_super_fast execute within microseconds even for higher indices. However, indices of 94 and higher cause a crash:

thread 'main' panicked at 'attempt to add with overflow', src/main.rs:42:35

Some performance measurements:

Enter n:
fib_super_fast(n) = 5 (0µs)
fib_fast(n)       = 5 (0µs)
fib(n)            = 5 (1µs)

Enter n:
fib_super_fast(n) = 6765 (1µs)
fib_fast(n)       = 6765 (10µs)
fib(n)            = 6765 (536µs)

Enter n:
fib_super_fast(n) = 102334155 (1µs)
fib_fast(n)       = 102334155 (54µs)
fib(n)            = 102334155 (1908011µs)

Enter n:
fib_super_fast(n) = 1134903170 (2µs)
fib_fast(n)       = 1134903170 (15µs)
fib(n)            = 1134903170 (21216762µs)

Enter n:
fib_super_fast(n) = 2880067194370816120 (2µs)
fib_fast(n)       = 2880067194370816120 (958µs)

Enter n:
fib_super_fast(n) = 12200160415121876738 (3µs)
fib_fast(n)       = 12200160415121876738 (152µs)

Enter n:
thread 'main' panicked at 'attempt to add with overflow', src/main.rs:42:35

Just for a nice style, you could factor out the returns as if is an expression...

fn fib_super_fast(n: u64, curr: u64, prev: u64) -> u64 {
  if n == 0 {
  } else {
    fib_super_fast(n - 1, curr + prev, curr)


Since writing my implementation I've remembered that the parameter i is unnecessary and you can decrease n instead until it's 0.

fn fib_super_fast(n: u64, curr: u64, prev: u64) -> u64 {
  if n <= 0 {
    return curr;

  return fib_super_fast(n - 1, curr + prev, curr);

By the way, you didn't set default values for curr and prev, how does that work, do you need to call it with fib_super_fast(n, 1, 0)?


Yes, I do. But I have to use fib_super_fast(n, 1, 1, 0) as my other implementations also begin with 1. The code for calling the fibonacci methods is:

fn main() {
  loop {
    println!("Enter n:");

    let mut n_str = String::new();
    io::stdin().read_line(&mut n_str).expect("Failed to read line");
    let n = user_input_to_int(n_str);

    let t0 = SystemTime::now();
    let fib_super_fast_n = fib_super_fast(n, 1, 1, 0);
    let t1 = SystemTime::now();
    println!("fib_super_fast(n) = {} ({}µs)", fib_super_fast_n, time_difference(t0, t1));

    let t0 = SystemTime::now();
    let fib_fast_n = fib_fast(n);
    let t1 = SystemTime::now();
    println!("fib_fast(n)       = {} ({}µs)", fib_fast_n, time_difference(t0, t1));

    let t0 = SystemTime::now();
    let fib_n = fib(n);
    let t1 = SystemTime::now();
    println!("fib(n)            = {} ({}µs)", fib_n, time_difference(t0, t1));

Technically lazy evaluation of a endless stream is iterative, not recursive, but anyway, here is a solution in Haskell:

fibonnaciNums = 0 : 1 : zipWith (+) fibonnaciNums (tail fibonnaciNums)

fibonnaci n        = last $ take n fibonnaciNums 
-- or even shorter:  fibonnaciNums !! n
#include <iostream>

template<long long i> long long fibonacci() {
    return fibonacci<i-1>() + fibonacci<i-2>();

template<> long long fibonacci<1>() {
    return 1;

template<> long long fibonacci<2>() {
    return 1;

int main() {
    std::cout << "Fibonacci of 27 is " << fibonacci<27>() << std::endl;
    return 0;

C++ can, of course, do it at build time with a bit of templates.

Here, we're definitely recursing - twice, because it's simpler. At runtime, it's just printing the value out that's been calculated by the compiler during the build.


Here's a Python variant for quite large numbers. Alas, due to recursion depth restrictions, any new calculated Fibonacci number should not have a larger sequence position than about 500 more than that of the highest already calculated.

def fib(a, F={}):
    if a in F:
        return F[a]
    if a < 2:
        return 1
    f = fib(a-1)
    F[a-1] = f
    return f + fib(a-2)

for i in range(0,50001,500):
    print("fib(%i) = %i"%(i,fib(i)))


v   >:1-\2-101O\101O+B

Tail-recursive #elixir (try your solution for 10000, mine works in 100ms)

defmodule Fib do
  def fib(curr \\ 1, acc \\ 0, n)
  def fib(_, acc, n) when n <= 0, do: acc
  def fib(curr, acc, n), do: fib(acc, curr + acc, n - 1)

(1..10) |> Enum.map(&Fib.fib/1) |> Enum.join(" → ") |> IO.puts

10_000 |> Fib.fib() |> to_string() |> String.length() |> IO.puts
1 → 1 → 2 → 3 → 5 → 8 → 13 → 21 → 34 → 55


Argh, I was going to write a similar one in Elixir! I do like your join with the arrow!


Common Lisp!

(defun fib (n &optional (curr 0) (next 1)) 
  (if (zerop n) 
      (fib (1- n) next (+ curr next))))

(and for the TCO crowd... it's implementation dependent, so YMMV)

def fib(arg):
  curr, prev = 1, 1
  n = int(arg)
  if n != arg or n <= 0:
    raise ValueError("Argument must be positive integer")
  if n <= 2:
    return 1
  for count in range(n - 2):
    curr, prev = curr + prev, curr
  return curr

Quick bit of Python. The error handling probably isn't complete, but Python has the useful benefit here that it has native, transparent, Big Number support - you can do fib(10000) if you want (or much higher if you have the memory).

But yeah, I just noticed Douglas wanted a recusrive algorithm, whereas I've done it iteratively without thinking. In general, iterative solutions will execute faster - though this isn't always the case.


I have haskell here with the best form of recursion: Self-recursion!

fibs = 1:1:zipWith (+) fibs (tail fibs)
fib n = fibs !! n

Here fibs is an infinite List of all fibonacci numbers, the !! function returns the nth element of the list.


I also have the boring tail recursive version here:

fib n = fibHelper n 1 1
    where fibHelper  0 a  _ = a
          fibHelper !n a !b = fibHelper (n-1) b (a+b)

Tail-recursive #ruby

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,  
  trace_instruction: false  

def fib(curr = 1, acc = 0, n)
  n <= 0 ? acc : fib(acc, curr + acc, n - 1)

#⇒ 2090

(1..10).map(&method(:fib)).join(" → ")
#⇒ "1 → 1 → 2 → 3 → 5 → 8 → 13 → 21 → 34 → 55"

I'll continue with it in R

fibR <- function(n) {
    if ((n == 0) | (n == 1)) 
        return(fibR(n-1) + fibR(n-2))

#include <iostream>

constexpr long long fibonacci(long long i) {
    if (i <= 2) {
        return 1LL;
    return fibonacci(i - 1) + fibonacci(i - 2);

int main() {
    std::cout << "Fibonacci of 27 is " << fibonacci(27) << std::endl;
    return 0;

Modern C++ can do it more simply, though - this uses constexpr to tell the compiler that it can calculate these at build time if it wants. Using a constexpr arg (here a literal), it probably will do, but we could also pass in a variable to make it calculate it at runtime.


An Emacs Lisp version. Warning!! This will likely freeze your Emacs!!

(defun fib(n)
          ((= n 0) 0)
          ((= n 1) 1)
          (t (+ (fib (- n 1)) (fib (- n 2))))))

Just realized it counts as a Common Lisp version too


I will be starting with python.

def fib(n):
   if n <=1:
      return 1
      return fib(n-1) + fib(n-2)

Being not tail-recursive it blows up for relatively big Ns.


As a Ruby fan, I'm sure glad Ruby has such a great ambassador in here.


I am using Kotlin here.

tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger { return if (n == 0) a else fibonacci(n-1, b, a+b) }

Another correct answer here :) tailrec directive has always confused me in Kotlin. Why not just silently apply tail recursion optimization if possible?


Also since your answers in this entire thread are a bit nitpicky, the non-recursive solutions are not incorrect per se, they just work on a smaller domain than ℕ.

I'd guess it's hard to efficiently detect tail recursion in the generated byte code, probably because the JVM was originally built without support for proper tail calls

Yes, that was my guess as well.

the non-recursive solutions are not incorrect per se, they just work on a smaller domain than ℕ.

I disagree. Either “works on a smaller domain than ℕ” should be stated upfront, with an exact maximal N this function works for, or it should accept any input.

Tail-recursive or not, no function accepts any input. Infinity is rather big, I can always find a number that not longer fits in the working memory of your computer. Does that make your solution incorrect?

Excuse the silly hyperbole, but on a site that also attracts a lot of new(ish) developers your self-indulgent overcorrectness on what OP explicitly called a fun "game" is a bit off-putting to be honest.

OK, if you indeed think that for new(ish) developers it’s better to stay unaware of important things, like solution correctness, ability to spot the limits of the solution, etc, I plain shut up :)

I always thought that it’s better to point out to mistakes, people grow that way, not when they are constantly told they are genius. But ok.

For people to grow from mistakes they need to listen to the person who points them out. To be that person, I'd reconsider my communication style.

There's nothing wrong with posting your own answer and discussing the merits of tail recursion and the problems with other solutions there. Posting a comment under every single answer seems a bit...too much.

Anyway, it's not my site, you're of course free to post whatever you want. But that may also invite people to comment on the limits of your communication style, so as long as you're cool with that ¯\(ツ)

Honestly, I dunno.

Sometimes it is clear to me that your point of view is correct and I, say, reconsider the communication style.

Other times, though, I am positive that some people listen to the knowledge/wisdom, despite how harsh is the communication style, and I could not care less about those who claim the communication style is the most important thing and if and only if the advice is given as to a 5yo nephew they listen to it. These thoughts make me leave comments everywhere so that the chance they are spotted by anybody really interested in growing is higher.

I did not come to an agreement with myself on the above and I jump from one communication style to the very opposite one, but my only intent is indeed to make them who need that to hear the voice.

Thanks for taking the time to type out this response!

Like you I'm not a native English speaker, and my native language (and culture) generally is also much more direct and — for lack of a better word — "confrontational" than English. That said I moved a lot over the last 16 years and spent almost half of that time in East and Southeast Asia, where communication tends to be very indirect and high context, and overall culture is extremely non-confrontational. This definitely had some influence on how I communicate nowadays.

I don't doubt that you have only the best intentions, and will keep that in mind for future occasions where I may feel tempted to butt in.

Yes. I guess the choice of words gave it away, though it’s not unique to that book. Also “The Geography Of Thought” and quite a few other books on (intercultural) communication.


@mudasobwa I think pointing out a defect, or even just something that can be improved is fine. However I do think that making your point once is good enough. Also I recommend an approach where you say something like “this works fine when N is small enough, but you can extend the domain of this function to larger input values if you avoid using recursion.” If you can make your point while remaining friendly, why not do so?

I do think that making your point once is good enough.

@nestedsoftware I do not care about how do I sound and what people would think about me, my approaches and my reputation. I gain reputation with the code I publish to open source, answers I give on SO, posts I publish here etc, not with blah-blah-blah in comments.

I address my replies mostly to newbies who might accidentally reach this post out and copy-paste the solution as is, thinking that once it was published in the Internets, it must be robust enough. If everybody will hate me and my communication skills, in exchange for I have taught a single person to what TCO is, I would be happy.

Respectfully, if you want to help newbies on a general issue such as recursion, just make a top-level comment addressing this problem. Show an example of the problem and suggest ways it can be fixed. That way, if the community deems the comment to be helpful, it will bubble up near the top of the discussion and it will be one of the first comments that newbies encounter.

In this manner, you won't be repeating the same comment all over the place, and you will have something clear that novices can wrap their minds around. In my opinion, making grumpy statements to the effect of "this crashes when the input reaches X" doesn't really help the very novices you say you most want to reach.

Edit: Added "in my opinion" :)

doesn't really help the very novices

You might be right. The only thing I do not get is why are you sure you are right. You are constantly suggesting to me how should I behave, stating everything like it was a holy truth. It is not. Put “IMHO”s here and there and maybe I’ll start considering this as deserving my attention.


Because different language runtimes have different execution models, so doing it automatically might not always be possible/feasible. Given that Scala — another JVM language — also has a @tailrec annotation I'd guess it's hard to efficiently detect tail recursion in the generated byte code, probably because the JVM was originally built without support for proper tail calls (unlike for example Scheme where tail call elimination is part of the standard since R5RS).

code of conduct - report abuse