<div class="gmail_quote">On 14 September 2012 18:30, Chris Angelico <span dir="ltr"><<a href="mailto:rosuav@gmail.com" target="_blank">rosuav@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div class="im">On Sat, Sep 15, 2012 at 2:15 AM, andrea crotti<br>
<<a href="mailto:andrea.crotti.0@gmail.com">andrea.crotti.0@gmail.com</a>> wrote:<br>
> The poor algorithm is much more close to the mathematical definition<br>
> than the smarter iterative one..  And in your second version you<br>
> include some ugly caching logic inside it, so why not using a<br>
> decorator then?<br>
<br>
</div>I learned Fibonacci as a sequence, not as a recursive definition. So<br>
the algorithm I coded (the non-caching one) is pretty much how I<br>
learned it in mathematics. But yes, you're right that the caching is<br>
inherent to the second version; and yes, that's where a decorator can<br>
make it a LOT cleaner.<br>
<br>
As a demo of recursion and decorators, your original function pair is<br>
definitely the best. But if you want to be able to calculate fib(n)<br>
for any n without blowing your stack, my version will scale much more<br>
safely.<br>
<br>
But then again, who actually ever needs fibonacci numbers?<br></blockquote><div><br></div><div>I thought the example was good, not because  a recursive fib is useful but because memoizing is. There are a lot of times one would like to memoize a function: not just recursive ones. Thus, the example of the decorator was valid.</div>

<div><br></div><div>[offtopic]</div><div>Anyhow, the "best" method has to be this:</div><div><br></div><div>>>> from decimal import Decimal as Dec</div><div>>>> def fib(n):</div><div>...     rootFive = Dec(5).sqrt()</div>

<div>...     phi = (1 + rootFive) / 2</div><div>...     return round(phi**n / rootFive)</div><div><div>>>> fib(100)</div><div>354224848179261915075</div></div><div> </div><div>It's just so obvious why it works.</div>

<div>[/offtopic]</div></div>