Star coder challenger : propose the best code to do the following

Question

We have Fib(1)=1, Fib(0)=1 and Fib(n)=Fib(n-1)+Fib(n-2) for n>=2

The challenge is to propose the best code to calculate Fib(n). You think this is too easy for you or you already did it ? Think again about how good your code is and propose your best solution, you'll be surprised...

Answer 1

https://code.sololearn.com/cC75CJN3PKu8/?ref=app

Answer 2

Yeah, quickest but it loses in precision :)

Answer 3

@swim quite cool !
But it is not possible to use it with user input :/

Answer 4

@VcC, I think that both your complex solution and the linear solution are the best (speed speaking). But respecting the KISS (keep it simple stupid) principle is something really important for maintainability purpose. What if, now, your superior ask you for U(n)=U(n-1)/2+2*U(n-2) ?

And your simple recursion is not the best recursive function as it creates and use a list. Go check mine, using tail recursion is a way better solution (when possible) with resistivity. It avoids StackOverflow problem and is still a "one call" recursive solution.

Answer 5

Hum, nice then !

Answer 6

Hum ... Apart from really small optimisation, I do not know how :/

Answer 7

So far you are the best, though :-)

Answer 8

Baptist you won this one. But look here for the quickest solution - by solving the recursion you can make a closed function. Also this codz compares the low efficiency of recursive versions (can be optimized by recursing on a couple of values). https://code.sololearn.com/c3Z8gCT6JqBJ/?ref=app

Answer 9

Up to high n it gives the exact answer. You can use python's decimal package with infinite precision. For very high N there might be a log(n) algorithm based on fast exponentiation of polynomials f(sqrt(5)).

Answer 10

Sure. Except linear and closed formula the rest where just directional examples of different styles. But recursion is VERY often excessively time consuming. Of course since a dev costs per year the equivalent of 10 PCs you might prefer an average dev and more PCs ;-)

Answer 11

@VcC, wrong ! Tail recursion is about the same as iteration in resource cost :)

Answer 12

In complexity yes. In overhead and stack manipulation, not so compared to a simple loop.

Answer 13

But tail recursion has not the classical recursion's stack manipulation as nothing more than the result of the recursive call is returned ^^

Answer 14

Nice one. Can still be optimized !

Answer 15

For low values of n no problem. But you will have lots of recursive calls. See the python version for dryer version !

Answer 16

Yes but the design is not good - lots of computation power lost in recursion. 100x cost factor compared to the best options.

Answer 17

It is not complex. You have several versions of the same code and a time of execution benchmark. The linear version very simple. And Imho double recursion is really not a good design - one that should never be done.

def fiblinear(p:int):
prec,res=1,1
for i in range(2,p):
prec,res=res,prec+res
return(res)