Douglas R Andreani

Posted on Aug 21, 2018

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

#challenge #beginners #fun

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 Fibonacci recursive algorithm on the comments. Are you in?

EDIT: this is not about having the fast/better code, just to have some fun

Oldest comments (51)

Douglas R Andreani • Aug 21 '18 • Edited

I will be starting with python.

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

Avalander • Aug 21 '18 • Edited

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

David Wickes • Aug 21 '18

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

Avalander • Aug 21 '18

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

David Wickes • Aug 23 '18 • Edited

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.

Ankit Kumar • Aug 21 '18 • Edited

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

Avalander • Aug 21 '18

And your point is...?

Slavius • Aug 21 '18

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

Console.WriteLine(
  Enumerable.Range(1, 10)
  .Skip(2)
  .Aggregate(
    new { Current = 1, Prev = 1 }, (x, index) => new { 
      Current = x.Prev + x.Current, Prev = x.Current }
  ).Current
);

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

Avalander • Aug 21 '18

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

Slavius • Aug 21 '18

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? ;)

Avalander • Aug 21 '18

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?

Slavius • Aug 21 '18 • Edited

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)
  .AsParallel()
  .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 ;)

Slavius • Aug 21 '18 • Edited

> #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);
1242044891
00:00:00.0025070
>

Douglas R Andreani • Aug 21 '18

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

Avalander • Aug 21 '18

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.

Avalander • Aug 21 '18 • Edited

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)
            b
            (fib-iter (+ a b) a (+ count 1))))
    (fib-iter 1 0 0))

Tested for values of n up to 10001.

Slavius • Aug 21 '18 • Edited

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;
            Console.WriteLine(
              Enumerable.Range(1, 10000)
              .Skip(2)
              .Aggregate(
                new { Current = (BigInteger)1, Prev = (BigInteger)1 }, (x, index) => new {
                    Current = x.Prev + x.Current,
                    Prev = x.Current
                }
              ).Current
            );
            Console.WriteLine(DateTime.Now - start);
            Console.ReadLine();
        }
    }
}

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
00:00:00.0245407

Slavius • Aug 21 '18 • Edited

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

Avalander • Aug 21 '18

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.

Slavius • Aug 21 '18 • Edited

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

Slavius • Aug 21 '18

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

Fabian Holzer • Aug 21 '18

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