{"id":26536,"date":"2017-12-20T21:41:14","date_gmt":"2017-12-20T16:11:14","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26536"},"modified":"2017-12-20T21:41:14","modified_gmt":"2017-12-20T16:11:14","slug":"python-programming-program-fibonacci-numbers","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-program-fibonacci-numbers\/","title":{"rendered":"Python Programming &#8211; Program for Fibonacci numbers"},"content":{"rendered":"<p>The Fibonacci numbers are the numbers in the following integer sequence.<span id=\"more-10120\"><\/span><\/p>\n<p>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \u2026\u2026..<\/p>\n<p>In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation<\/p>\n<pre>    F<sub>n<\/sub> = F<sub>n-1<\/sub> + F<sub>n-2<\/sub><\/pre>\n<p>with seed values<\/p>\n<pre>F<sub>0<\/sub> = 0 and F<sub>1<\/sub> = 1.<\/pre>\n<p>Write a function <em>int fib(int n)<\/em> that returns F<sub>n<\/sub>. For example, if <em>n<\/em> = 0, then <em>fib()<\/em> should return 0. If n = 1, then it should return 1. For n > 1, it should return F<sub>n-1<\/sub> + F<sub>n-2<\/sub><\/p>\n<pre>For n = 9\r\nOutput:34<\/pre>\n<p>Following are different methods to get the nth Fibonacci number.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Method 1 ( Use recursion ) <\/strong><br \/>\nA simple method that is a direct recursive implementation mathematical recurrence relation given above.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Function%20for%20nth%20Fibonacci%20number%0A%20%0Adef%20Fibonacci(n)%3A%0A%20%20%20%20if%20n%3C0%3A%0A%20%20%20%20%20%20%20%20print(%22Incorrect%20input%22)%0A%20%20%20%20%23%20First%20Fibonacci%20number%20is%200%0A%20%20%20%20elif%20n%3D%3D1%3A%0A%20%20%20%20%20%20%20%20return%200%0A%20%20%20%20%23%20Second%20Fibonacci%20number%20is%201%0A%20%20%20%20elif%20n%3D%3D2%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%20Fibonacci(n-1)%2BFibonacci(n-2)%0A%20%0A%23%20Driver%20Program%0A%20%0Aprint(Fibonacci(9))\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output<\/p>\n<pre>34<\/pre>\n<p><em>Time Complexity:<\/em> T(n) = T(n-1) + T(n-2) which is exponential.<br \/>\nWe can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.<\/p>\n<pre>                         fib(5)   \r\n                     \/             \\     \r\n               fib(4)                fib(3)   \r\n             \/      \\                \/     \\\r\n         fib(3)      fib(2)         fib(2)    fib(1)\r\n        \/     \\        \/    \\       \/    \\  \r\n  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)\r\n  \/    \\\r\nfib(1) fib(0)\r\n<\/pre>\n<p><em>Extra Space:<\/em> O(n) if we consider the function call stack size, otherwise O(1).<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Method 2 ( Use Dynamic Programming )<\/strong><br \/>\nWe can avoid the repeated work done is the method 1 by storing the Fibonacci numbers calculated so far.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Function%20for%20nth%20fibonacci%20number%20-%20Dynamic%20Programing%0A%23%20Taking%201st%20two%20fibonacci%20nubers%20as%200%20and%201%0A%20%0AFibArray%20%3D%20%5B0%2C1%5D%0A%20%0Adef%20fibonacci(n)%3A%0A%20%20%20%20if%20n%3C0%3A%0A%20%20%20%20%20%20%20%20print(%22Incorrect%20input%22)%0A%20%20%20%20elif%20n%3C%3Dlen(FibArray)%3A%0A%20%20%20%20%20%20%20%20return%20FibArray%5Bn-1%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20temp_fib%20%3D%20fibonacci(n-1)%2Bfibonacci(n-2)%0A%20%20%20%20%20%20%20%20FibArray.append(temp_fib)%0A%20%20%20%20%20%20%20%20return%20temp_fib%0A%20%0A%23%20Driver%20Program%0A%20%0Aprint(fibonacci(9))\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>34<\/pre>\n<p><em>Time Complexity:<\/em> O(n)<br \/>\n<em>Extra Space: <\/em>O(n)<\/p>\n<p><strong>Method 3 ( Space Optimized Method 2 )<\/strong><br \/>\nWe can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Function%20for%20nth%20fibonacci%20number%20-%20Space%20Optimisataion%0A%23%20Taking%201st%20two%20fibonacci%20numbers%20as%200%20and%201%0A%20%0Adef%20fibonacci(n)%3A%0A%20%20%20%20a%20%3D%200%0A%20%20%20%20b%20%3D%201%0A%20%20%20%20if%20n%20%3C%200%3A%0A%20%20%20%20%20%20%20%20print(%22Incorrect%20input%22)%0A%20%20%20%20elif%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%20a%0A%20%20%20%20elif%20n%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20return%20b%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(2%2Cn)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20c%20%3D%20a%20%2B%20b%0A%20%20%20%20%20%20%20%20%20%20%20%20a%20%3D%20b%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20%3D%20c%0A%20%20%20%20%20%20%20%20return%20b%0A%20%0A%23%20Driver%20Program%0A%20%0Aprint(fibonacci(9))\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<p><em>Time Complexity:<\/em> O(n)<br \/>\n<em>Extra Space: <\/em>O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Python Programming &#8211; Program for Fibonacci numbers &#8211; Dynamic Programming The Fibonacci numbers are the numbers in the following integer sequence.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,4148],"tags":[72847,72842,72845,70483,72848,72840,72852,79066,79077,74977,79103,79115,79113,72855,72853,79111,74961,79114,74934,79116,79106,72851],"class_list":["post-26536","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-python","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-problems-on-dynamic-programming","tag-program-for-fibonacci-numbers","tag-program-for-fibonacci-series","tag-python-program-for-fibonacci-series","tag-python-program-to-find-fibonacci-numbers-using-dynamic-programming","tag-python-program-to-find-fibonacci-series","tag-python-program-to-print-fibonacci-series","tag-simple-dynamic-programming-example","tag-types-of-dynamic-programming","tag-write-a-program-in-python-for-fibonacci-series","tag-write-a-program-to-generate-the-fibonacci-series","tag-write-a-program-to-generate-the-fibonacci-series-in-python","tag-write-a-program-to-print-fibonacci-series","tag-write-a-python-program-for-fibonacci-series","tag-write-a-python-program-to-print-nth-fibonacci-number","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26536","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26536"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26536\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26536"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26536"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26536"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}