{"id":33,"date":"2011-05-28T00:14:38","date_gmt":"2011-05-28T00:14:38","guid":{"rendered":"http:\/\/www.anattasoftware.com\/blog\/?p=33"},"modified":"2012-12-25T22:40:47","modified_gmt":"2012-12-25T22:40:47","slug":"python-fibonacci-list","status":"publish","type":"post","link":"https:\/\/tech.avant.net\/q\/python-fibonacci-list\/","title":{"rendered":"python Fibonacci list"},"content":{"rendered":"

The Fibonacci sequence in python looks something like this<\/p>\n

\ndef fib(n):\n    if n == 0:\n        return 0\n    elif n == 1:\n        return 1\n    else:\n        return fib(n-1) + fib(n-2)\n<\/pre>\n
But expect stack overflows for even small values of n, e.g., fib(60) will require over 3 trillion function calls. You can use the Fibonacci sequence itself to compute the number of function calls.<\/p>\n
I.e., both fib(0) and fib(1) require only one function call,
\nfib(2) will call fib(1) and fib(0) for a total of 3 function calls,
\nfib(3) will call fib(2) and fib(1) for a total of 1+3+1=5 function calls,
\nfib(4) will call fib(3) and fib(2) for a total of 1+5+3=9 function calls,
\nfib(5) will call fib(4) and fib(2) for a total of 1+9+5=15 function calls, and so on…<\/p>\n
In fact, for any n > 1, fib(0) will be called exactly fib(n-2) times and fib(1..n) will be called fib(n-i) times (for every i 1..n).  In python you can compute this as follows:<\/p>\n
\ndef recursive_fib_counter(n):\n    count = fib(n-2)\n    for k in range(1,n):\n        count += fib(n-k)\n    return count\n<\/pre>\n
This will produce an interesting series: 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, … which is known as the Leonardo Numbers. Dijkstra<\/a> wrote about their relationship to the Fibonacci sequence in 1981. And here I thought I was on to something.<\/p>\n
Anyway, this is all well and great, but obviously inefficient– a Fibonacci sequence ought to be computed linearly, i.e., O(n) time.  And to make this interesting, we can utilize python magic to create a Fibonacci object that behaves like a list.<\/p>\n
\nclass Fibonacci(object):\n    \"\"\"lazy loading Fibonacci sequence\"\"\"\n    def __init__(self):\n        self.fib = [0,1]\n\n    def __getitem__(self, n):\n        self._fib(n)\n        return self.fib[n]\n\n    def __getslice__(self, start, end):\n        self._fib(max(start,end,len(self.fib)))\n        return self.fib[start:end]\n\n    def __call__(self, n):\n        return self.__getitem__(n)\n\n    def _fib(self, n):\n        for i in range(len(self.fib), n+1):\n            self.fib.insert(i, self.fib[i-1] + self.fib[i-2])\n        return self.fib[n]\n<\/pre>\n
This way you can create a Fibonacci sequence, access it as a callable function or as a list, including list splicing, behold:<\/p>\n
\n>>> fib = Fibonacci()\n>>> fib[5]\n5\n>>> fib[0:10]\n[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]\n>>> fib(60)\n1548008755920L\n>>> from decimal import *\n>>> phi = Decimal(fib(9999)) \/ Decimal(fib(9998))\n>>> phi\nDecimal('1.618033988749894848204586834')\n<\/pre>\n
Best of all it’s extremely fast, in the recursive model fib(9999) would be computationally impossible, even fib(500) would require more than a google of recursive function calls, and fib(9999) would require more than 102090<\/sup> function calls.<\/p>\n
And while the Fibonacci object is iterable, it’s also infinite (like the Fibonacci sequence itself), so it’s best to iterate over a list returned by a splice rather than iterate over the object itself (which again, is computationally infinite), e.g.,<\/p>\n
\n>>> fib = Fibonacci()\n>>> for i in fib[0:5]:\n\tprint(i)\n\n0\n1\n1\n2\n3\n>>> \n>>> ## I'll leave this as an exercise for the reader, go on, it's kind of fun\n>>> ##  (you'll probably want to Ctrl-C at some point)\n>>> for i in fib:\n\tprint(i)\n        ...\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
The Fibonacci sequence in python looks something like this def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) But expect stack overflows for even small values of n, e.g., fib(60) will require over 3 trillion function calls. You can use the Fibonacci sequence itself to […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts\/33"}],"collection":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/comments?post=33"}],"version-history":[{"count":1,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts\/33\/revisions"}],"predecessor-version":[{"id":740,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts\/33\/revisions\/740"}],"wp:attachment":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/media?parent=33"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/categories?post=33"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/tags?post=33"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}