## DEV Community 👩‍💻👨‍💻

Douglas R Andreani

Posted on

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

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

Rob Hoelz

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

union

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

select a from fib limit 10;
``````

Slavius

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

``````SET STATISTICS TIME,PROFILE ON

DECLARE @MAX SMALLINT
SET @MAX = 1474

SELECT TOP 1 s.Fib FROM (
SELECT
FLOOR(POWER(( 1 + SQRT(5) ) / 2.0, number) / SQRT(5) + 0.5) AS Fib
FROM master..spt_values
WHERE TYPE = 'p' AND number BETWEEN 1 AND @MAX
) AS s
ORDER BY s.Fib DESC
``````

Ross Henderson

Here it is in Oracle SQL:

``````with FIBONACCI (i, SPIRAL, PREV) as
(
select
1 i, 0 SPIRAL, cast(null as number) PREV
from
DUAL
union all
select
f1.i + 1 i, f1.SPIRAL + nvl(f1.PREV,1) SPIRAL, f1.SPIRAL PREV
from
FIBONACCI f1
where
f1.i < 605
)

select SPIRAL from FIBONACCI order by i;
``````

The limit of 605 is the limit before numeric overflow.

Avalander

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

Max Cerrina

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)

Avalander • Edited on

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 • Edited on

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.

David Wickes

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

Avalander

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

Slavius

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

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

Slavius

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

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 • Edited on

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

Avalander • Edited on

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

Avalander

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.

Douglas R Andreani

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

Slavius • Edited on

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

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.

Felix Edelmann

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:

Some performance measurements:

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

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

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

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

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

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

Enter n:
94
``````

David Wickes

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

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

Avalander • Edited on

Nice!

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

Felix Edelmann

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();
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));
}
}
``````

Fabian Holzer

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

Slavius • Edited on

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);
}
}
}
``````
``````33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
00:00:00.0245407
``````

Dave Cridland
``````#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.

Marvodor

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

Sam Ferree
``````v   >:1-\2-101O\101O+B
:1`|
>\$1B
>&:!#v_101O.55+,
@
``````

stereobooster • Edited on

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