The Fibonacci numbers are the numbers in the following integer sequence.<\/p>\n
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \u2026\u2026..<\/p>\n
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation<\/p>\n
Fn = Fn-1 + Fn-2
\nwith seed values<\/p>\n
F0 = 0 and F1 = 1.<\/p>\n
Write a function int fib(int n) that returns Fn. For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return Fn-1 + Fn-2<\/p>\n
For n = 9
\nOutput:34
\nFollowing are different methods to get the nth Fibonacci number.<\/p>\n[ad type=\u201dbanner\u201d]\n
Method 1 ( Use recursion )
\nA simple method that is a direct recursive implementation mathematical recurrence relation given above.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2FFibonacci%20Series%20using%20Recursion%0A%23include%3Cstdio.h%3E%0Aint%20fib(int%20n)%0A%7B%0A%20%20%20if%20(n%20%3C%3D%201)%0A%20%20%20%20%20%20return%20n%3B%0A%20%20%20return%20fib(n-1)%20%2B%20fib(n-2)%3B%0A%7D%0A%20%0Aint%20main%20()%0A%7B%0A%20%20int%20n%20%3D%209%3B%0A%20%20printf(%22%25d%22%2C%20fib(n))%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dc program1\u2033 highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output<\/p>\n
34<\/pre>\nTime Complexity:<\/em> T(n) = T(n-1) + T(n-2) which is exponential.<\/p>\n
We 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
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)<\/pre>\nExtra Space:<\/em> O(n) if we consider the function call stack size, otherwise O(1).<\/p>\n[ad type=\u201dbanner\u201d]\n
Method 2 ( Use Dynamic Programming )<\/strong>
\nWe can avoid the repeated work done is the method 1 by storing the Fibonacci numbers calculated so far.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2FFibonacci%20Series%20using%20Dynamic%20Programming%0A%23include%3Cstdio.h%3E%0A%20%0Aint%20fib(int%20n)%0A%7B%0A%20%20%2F*%20Declare%20an%20array%20to%20store%20Fibonacci%20numbers.%20*%2F%0A%20%20int%20f%5Bn%2B1%5D%3B%0A%20%20int%20i%3B%0A%20%0A%20%20%2F*%200th%20and%201st%20number%20of%20the%20series%20are%200%20and%201*%2F%0A%20%20f%5B0%5D%20%3D%200%3B%0A%20%20f%5B1%5D%20%3D%201%3B%0A%20%0A%20%20for%20(i%20%3D%202%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20%20%20%2F*%20Add%20the%20previous%202%20numbers%20in%20the%20series%0A%20%20%20%20%20%20%20%20%20and%20store%20it%20*%2F%0A%20%20%20%20%20%20f%5Bi%5D%20%3D%20f%5Bi-1%5D%20%2B%20f%5Bi-2%5D%3B%0A%20%20%7D%0A%20%0A%20%20return%20f%5Bn%5D%3B%0A%7D%0A%20%0Aint%20main%20()%0A%7B%0A%20%20int%20n%20%3D%209%3B%0A%20%20printf(%22%25d%22%2C%20fib(n))%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dc program2\u2033 highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nOutput:<\/p>\n
34<\/pre>\nTime Complexity:<\/em> O(n)
\nExtra Space: <\/em>O(n)<\/p>\n[ad type=\u201dbanner\u201d]\nMethod 3 ( Space Optimized Method 2 )<\/strong>
\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=\u201dc\u201d manual=\u201d%2F%2F%20Fibonacci%20Series%20using%20Space%20Optimized%20Method%0A%23include%3Cstdio.h%3E%0Aint%20fib(int%20n)%0A%7B%0A%20%20int%20a%20%3D%200%2C%20b%20%3D%201%2C%20c%2C%20i%3B%0A%20%20if(%20n%20%3D%3D%200)%0A%20%20%20%20return%20a%3B%0A%20%20for%20(i%20%3D%202%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20%20c%20%3D%20a%20%2B%20b%3B%0A%20%20%20%20%20a%20%3D%20b%3B%0A%20%20%20%20%20b%20%3D%20c%3B%0A%20%20%7D%0A%20%20return%20b%3B%0A%7D%0A%20%0Aint%20main%20()%0A%7B%0A%20%20int%20n%20%3D%209%3B%0A%20%20printf(%22%25d%22%2C%20fib(n))%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dc program3\u2033 highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nTime Complexity: O(n)
\nExtra Space: O(1)<\/p>\n[ad type=\u201dbanner\u201d]\nMethod 4<\/strong> ( Using power of the matrix {{1,1},{1,0}} )
\nThis another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.<\/p>\n\u00a0<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%20%0A%2F*%20Helper%20function%20that%20multiplies%202%20matrices%20F%20and%20M%20of%20size%202*2%2C%20and%0A%20%20puts%20the%20multiplication%20result%20back%20to%20F%5B%5D%5B%5D%20*%2F%0Avoid%20multiply(int%20F%5B2%5D%5B2%5D%2C%20int%20M%5B2%5D%5B2%5D)%3B%0A%20%0A%2F*%20Helper%20function%20that%20calculates%20F%5B%5D%5B%5D%20raise%20to%20the%20power%20n%20and%20puts%20the%0A%20%20result%20in%20F%5B%5D%5B%5D%0A%20%20Note%20that%20this%20function%20is%20designed%20only%20for%20fib()%20and%20won\u2019t%20work%20as%20general%0A%20%20power%20function%20*%2F%0Avoid%20power(int%20F%5B2%5D%5B2%5D%2C%20int%20n)%3B%0A%20%0Aint%20fib(int%20n)%0A%7B%0A%20%20int%20F%5B2%5D%5B2%5D%20%3D%20%7B%7B1%2C1%7D%2C%7B1%2C0%7D%7D%3B%0A%20%20if%20(n%20%3D%3D%200)%0A%20%20%20%20%20%20return%200%3B%0A%20%20power(F%2C%20n-1)%3B%0A%20%0A%20%20return%20F%5B0%5D%5B0%5D%3B%0A%7D%0A%20%0Avoid%20multiply(int%20F%5B2%5D%5B2%5D%2C%20int%20M%5B2%5D%5B2%5D)%0A%7B%0A%20%20int%20x%20%3D%20%20F%5B0%5D%5B0%5D*M%5B0%5D%5B0%5D%20%2B%20F%5B0%5D%5B1%5D*M%5B1%5D%5B0%5D%3B%0A%20%20int%20y%20%3D%20%20F%5B0%5D%5B0%5D*M%5B0%5D%5B1%5D%20%2B%20F%5B0%5D%5B1%5D*M%5B1%5D%5B1%5D%3B%0A%20%20int%20z%20%3D%20%20F%5B1%5D%5B0%5D*M%5B0%5D%5B0%5D%20%2B%20F%5B1%5D%5B1%5D*M%5B1%5D%5B0%5D%3B%0A%20%20int%20w%20%3D%20%20F%5B1%5D%5B0%5D*M%5B0%5D%5B1%5D%20%2B%20F%5B1%5D%5B1%5D*M%5B1%5D%5B1%5D%3B%0A%20%0A%20%20F%5B0%5D%5B0%5D%20%3D%20x%3B%0A%20%20F%5B0%5D%5B1%5D%20%3D%20y%3B%0A%20%20F%5B1%5D%5B0%5D%20%3D%20z%3B%0A%20%20F%5B1%5D%5B1%5D%20%3D%20w%3B%0A%7D%0A%20%0Avoid%20power(int%20F%5B2%5D%5B2%5D%2C%20int%20n)%0A%7B%0A%20%20int%20i%3B%0A%20%20int%20M%5B2%5D%5B2%5D%20%3D%20%7B%7B1%2C1%7D%2C%7B1%2C0%7D%7D%3B%0A%20%0A%20%20%2F%2F%20n%20-%201%20times%20multiply%20the%20matrix%20to%20%7B%7B1%2C0%7D%2C%7B0%2C1%7D%7D%0A%20%20for%20(i%20%3D%202%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20multiply(F%2C%20M)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20int%20n%20%3D%209%3B%0A%20%20printf(%22%25d%22%2C%20fib(n))%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dc program4\u2033 highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Time Complexity: O(n)
\nExtra Space: O(1)
\nMethod 5 ( Optimized Method 4 )
\nThe method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the prevous method (Similar to the optimization done in this post)<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%20%0Avoid%20multiply(int%20F%5B2%5D%5B2%5D%2C%20int%20M%5B2%5D%5B2%5D)%3B%0A%20%0Avoid%20power(int%20F%5B2%5D%5B2%5D%2C%20int%20n)%3B%0A%20%0A%2F*%20function%20that%20returns%20nth%20Fibonacci%20number%20*%2F%0Aint%20fib(int%20n)%0A%7B%0A%20%20int%20F%5B2%5D%5B2%5D%20%3D%20%7B%7B1%2C1%7D%2C%7B1%2C0%7D%7D%3B%0A%20%20if%20(n%20%3D%3D%200)%0A%20%20%20%20return%200%3B%0A%20%20power(F%2C%20n-1)%3B%0A%20%20return%20F%5B0%5D%5B0%5D%3B%0A%7D%0A%20%0A%2F*%20Optimized%20version%20of%20power()%20in%20method%204%20*%2F%0Avoid%20power(int%20F%5B2%5D%5B2%5D%2C%20int%20n)%0A%7B%0A%20%20if(%20n%20%3D%3D%200%20%7C%7C%20n%20%3D%3D%201)%0A%20%20%20%20%20%20return%3B%0A%20%20int%20M%5B2%5D%5B2%5D%20%3D%20%7B%7B1%2C1%7D%2C%7B1%2C0%7D%7D%3B%0A%20%0A%20%20power(F%2C%20n%2F2)%3B%0A%20%20multiply(F%2C%20F)%3B%0A%20%0A%20%20if%20(n%252%20!%3D%200)%0A%20%20%20%20%20multiply(F%2C%20M)%3B%0A%7D%0A%20%0Avoid%20multiply(int%20F%5B2%5D%5B2%5D%2C%20int%20M%5B2%5D%5B2%5D)%0A%7B%0A%20%20int%20x%20%3D%20%20F%5B0%5D%5B0%5D*M%5B0%5D%5B0%5D%20%2B%20F%5B0%5D%5B1%5D*M%5B1%5D%5B0%5D%3B%0A%20%20int%20y%20%3D%20%20F%5B0%5D%5B0%5D*M%5B0%5D%5B1%5D%20%2B%20F%5B0%5D%5B1%5D*M%5B1%5D%5B1%5D%3B%0A%20%20int%20z%20%3D%20%20F%5B1%5D%5B0%5D*M%5B0%5D%5B0%5D%20%2B%20F%5B1%5D%5B1%5D*M%5B1%5D%5B0%5D%3B%0A%20%20int%20w%20%3D%20%20F%5B1%5D%5B0%5D*M%5B0%5D%5B1%5D%20%2B%20F%5B1%5D%5B1%5D*M%5B1%5D%5B1%5D%3B%0A%20%0A%20%20F%5B0%5D%5B0%5D%20%3D%20x%3B%0A%20%20F%5B0%5D%5B1%5D%20%3D%20y%3B%0A%20%20F%5B1%5D%5B0%5D%20%3D%20z%3B%0A%20%20F%5B1%5D%5B1%5D%20%3D%20w%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20int%20n%20%3D%209%3B%0A%20%20printf(%22%25d%22%2C%20fib(9))%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC program5\u2033 highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nTime Complexity: <\/em>O(Logn)<\/strong>
\nExtra Space:<\/em> O(Logn) if we consider the function call stack size, otherwise O(1).<\/p>\n[ad type=\u201dbanner\u201d]\nMethod 6 (O(Log n) Time)<\/strong>
\nBelow is one more interesting recurrence formula that can be used to find n\u2019th Fibonacci Number in O(Log n) time.<\/p>\nIf n is even then k = n\/2:\r\nF(n) = [2*F(k-1) + F(k)]*F(k)\r\n\r\nIf n is odd then k = (n + 1)\/2\r\nF(n) = F(k)*F(k) + F(k-1)*F(k-1)<\/pre>\nHow does this formula work?
\nThe formula can be derived from above matrix equation.
\nfibonaccimatrix<\/p>\nTaking determinant on both sides, we get
\n(-1)n = Fn+1Fn-1 \u2013 Fn2
\nMoreover, since AnAm = An+m for any square matrix A, the following identities can be derived (they are obtained form two different coefficients of the matrix product)<\/p>\nFmFn + Fm-1Fn-1 = Fm+n-1<\/p>\n
By putting n = n+1,<\/p>\n
FmFn+1 + Fm-1Fn = Fm+n<\/p>\n
Putting m = n<\/p>\n
F2n-1 = Fn2 + Fn-12<\/p>\n
F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (Source: Wiki)<\/p>\n
To get the formula to be proved, we simply need to do following
\nIf n is even, we can put k = n\/2
\nIf n is odd, we can put k = (n+1)\/2<\/p>\nBelow is C++ implementation of above idea.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%2B%2B%20Program%20to%20find%20n\u2019th%20fibonacci%20Number%20in%0A%2F%2F%20with%20O(Log%20n)%20arithmatic%20operations%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aconst%20int%20MAX%20%3D%201000%3B%0A%20%0A%2F%2F%20Create%20an%20array%20for%20memoization%0Aint%20f%5BMAX%5D%20%3D%20%7B0%7D%3B%0A%20%0A%2F%2F%20Returns%20n\u2019th%20fuibonacci%20number%20using%20table%20f%5B%5D%0Aint%20fib(int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20cases%0A%20%20%20%20if%20(n%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20if%20(n%20%3D%3D%201%20%7C%7C%20n%20%3D%3D%202)%0A%20%20%20%20%20%20%20%20return%20(f%5Bn%5D%20%3D%201)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20fib(n)%20is%20already%20computed%0A%20%20%20%20if%20(f%5Bn%5D)%0A%20%20%20%20%20%20%20%20return%20f%5Bn%5D%3B%0A%20%0A%20%20%20%20int%20k%20%3D%20(n%20%26%201)%3F%20(n%2B1)%2F2%20%3A%20n%2F2%3B%0A%20%0A%20%20%20%20%2F%2F%20Applyting%20above%20formula%20%5BNote%20value%20n%261%20is%201%0A%20%20%20%20%2F%2F%20if%20n%20is%20odd%2C%20else%200.%0A%20%20%20%20f%5Bn%5D%20%3D%20(n%20%26%201)%3F%20(fib(k)*fib(k)%20%2B%20fib(k-1)*fib(k-1))%0A%20%20%20%20%20%20%20%20%20%20%20%3A%20(2*fib(k-1)%20%2B%20fib(k))*fib(k)%3B%0A%20%0A%20%20%20%20return%20f%5Bn%5D%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20n%20%3D%209%3B%0A%20%20%20%20printf(%22%25d%20%22%2C%20fib(n))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Program 6\u2033 highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output :<\/p>\n
34<\/pre>\nTime complexity of this solution is O(Log n) as we divide the problem to half in every recursive call.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
C Programming Fibonacci numbers – Mathematical algorithms – The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,83563,74058],"tags":[74939,71157,74988,75004,69955,74999,74996,75003,74995,71152,75007,74080,70077,72112,72113,70972,74997,75006,75002,74992,74998,75001,74989,75005,74950,74076,74975,74951,74938,74940,74072,74945,72439,74060,72468,74066,70848,74952,74941,74935,74987,74949,75000,74994,74991,74990,74290,74993,74934,74942],"class_list":["post-25725","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-fibonacci-numbers","category-mathematical-algorithms","tag-algorithm-of-fibonacci-series","tag-bubble-sort-c-program","tag-c-language-graphics","tag-c-language-online-test","tag-c-language-operator","tag-c-language-questions-and-answers","tag-c-language-structure","tag-c-language-syllabus","tag-c-language-theory","tag-c-program-for-bubble-sort","tag-c-program-for-factorial","tag-c-program-for-fibonacci-series","tag-c-program-for-linear-search","tag-c-program-for-palindrome","tag-c-program-for-prime-number","tag-c-program-for-selection-sort","tag-c-program-sample","tag-c-program-structure","tag-c-programming-pointers","tag-c-programming-question-bank","tag-c-programming-question-paper","tag-c-programming-quiz","tag-c-programming-series-examples","tag-download-c-language","tag-fibonacci","tag-fibonacci-c-program","tag-fibonacci-formula","tag-fibonacci-java","tag-fibonacci-number-program-in-java","tag-fibonacci-program","tag-fibonacci-program-in-c","tag-fibonacci-series","tag-fibonacci-series-algorithm","tag-fibonacci-series-c-program","tag-fibonacci-series-in-c-using-recursion-with-explanation","tag-for-loop-c-programming","tag-for-loop-in-c-programming","tag-how-to-calculate-fibonacci","tag-java-fibonacci","tag-java-program-fibonacci","tag-modular-programming-in-c","tag-number-series-program-in-c","tag-online-c-programming","tag-online-c-programming-test","tag-programs-on-recursion-in-c","tag-recursion-in-c-programming-example","tag-recursion-program-in-c","tag-structure-in-c-programming","tag-write-a-program-to-print-fibonacci-series","tag-write-ac-program-to-generate-fibonacci-series"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25725","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25725"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25725\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25725"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25725"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25725"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}