On 14 September 2012 18:30, Chris Angelico <ros...@gmail.com> wrote: > On Sat, Sep 15, 2012 at 2:15 AM, andrea crotti > <andrea.crott...@gmail.com> wrote: > > The poor algorithm is much more close to the mathematical definition > > than the smarter iterative one.. And in your second version you > > include some ugly caching logic inside it, so why not using a > > decorator then? > > I learned Fibonacci as a sequence, not as a recursive definition. So > the algorithm I coded (the non-caching one) is pretty much how I > learned it in mathematics. But yes, you're right that the caching is > inherent to the second version; and yes, that's where a decorator can > make it a LOT cleaner. > > As a demo of recursion and decorators, your original function pair is > definitely the best. But if you want to be able to calculate fib(n) > for any n without blowing your stack, my version will scale much more > safely. > > But then again, who actually ever needs fibonacci numbers? >
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. [offtopic] Anyhow, the "best" method has to be this: >>> from decimal import Decimal as Dec >>> def fib(n): ... rootFive = Dec(5).sqrt() ... phi = (1 + rootFive) / 2 ... return round(phi**n / rootFive) >>> fib(100) 354224848179261915075 It's just so obvious why it works. [/offtopic]
-- http://mail.python.org/mailman/listinfo/python-list
