{"id":4311,"date":"2026-06-06T15:56:48","date_gmt":"2026-06-06T10:26:48","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=4311"},"modified":"2026-06-06T15:56:48","modified_gmt":"2026-06-06T10:26:48","slug":"implementing-fibonacci-sequence-in-c","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2026\/06\/06\/implementing-fibonacci-sequence-in-c\/","title":{"rendered":"Implementing Fibonacci Sequence in C++"},"content":{"rendered":"

The Fibonacci<\/strong><\/em> sequence is one of the most discussed examples in computer science. One reason is that it is a simple but great example of recursion. It also helps us in understanding the trade-offs between time snd space complexity.<\/p>\n

I today\u2019s article, I will implement Fibonacci<\/strong><\/em> sequence in C++<\/strong><\/em> in four different ways and also share the complexity numbers.<\/p>\n

For those who need a refresher: the Fibonacci<\/strong><\/em> sequence starts with 0 and 1, and each subsequent number is the sum of the two before it.<\/p>\n

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …<\/span><\/p>\n

Formally: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for all n > 1.<\/strong><\/em><\/p>\n

Implementation 1: Naive Recursion<\/strong><\/span><\/p>\n

The mathematical definition almost directly translates to code:<\/p>\n

\"Recursive<\/a>
Recursive Implementation<\/strong><\/figcaption><\/figure>\n

What is wrong with this algorithm? The time complexity is O(2^n)<\/strong><\/em> – that is exponential! The implementation might be OK for small values of N, but as N increases, the time complexity increases exponentially! Space complexity is just O(N)<\/strong><\/em>.<\/p>\n

Implementation 2: Recursion with Memoization<\/strong><\/span><\/p>\n

How can we do better? If we manage to \u201cremember\u201d<\/strong><\/em> previous call results, we don\u2019t have to recompute already computed values. This will definitely save a lot of time! Here is an implementation that uses \u201cmemoization\u201d<\/strong><\/em>.<\/p>\n

\"Recursion<\/a>
Recursion with Memoization<\/strong><\/figcaption><\/figure>\n

I hope you get the logic. What is the complexity this time? Both Space and Time complexities are O(N)<\/strong><\/em>!<\/p>\n

Implementation 3: Using Iteration<\/strong><\/span><\/p>\n

What if we decide to use \u201citeration\u201d<\/strong><\/em> instead of \u201crecursion\u201d<\/strong><\/em>? Here is an implementation.<\/p>\n

\"Using<\/a>
Using Iteration<\/strong><\/figcaption><\/figure>\n

If the code looks a bit weird, it is only because I have used std::tie<\/strong><\/em> to advance both the state variables simultaneously in a single step without using any temporary variable.<\/p>\n

As you can guess, the time complexity is O(N)<\/strong><\/em> and the space complexity is O(1)<\/strong><\/em>! The most efficient implementation of all!<\/p>\n

Implementation 4: Using co_yield<\/strong><\/span><\/p>\n

The final implementation uses C++23<\/strong><\/em>\u00a0std::generator<\/strong><\/em> idea and is implemented as a coroutine. The \u201cco_yield\u201d<\/strong><\/em> keyword suspends the function mid-execution, hands a value back to the caller, and resumes exactly where it left off on the next request. The underlying implementation uses iteration.<\/p>\n

\"Using<\/a>
Using std::generator c_yield<\/strong><\/figcaption><\/figure>\n

Here also, the time complexity is O(N)<\/strong><\/em> and the space complexity is O(1)<\/strong><\/em>.<\/p>\n

I enjoyed revisiting fibonacci implementation after decades! Hope you find this article useful and interesting!<\/p>\n

You can view the source code inside Compiler Explorer<\/strong><\/em><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

The Fibonacci sequence is one of the most discussed examples in computer science. One reason is that it is a simple but great example of recursion. It also helps us in understanding the trade-offs between time snd space complexity. I today\u2019s article, I will implement Fibonacci sequence in C++ in four different ways and also […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[49,17],"tags":[67,460],"class_list":["post-4311","post","type-post","status-publish","format-standard","hentry","category-c","category-programming","tag-c","tag-fibonacci-numbers"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-17x","jetpack-related-posts":[{"id":2383,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/26\/lparallel-a-parallel-programming-library\/","url_meta":{"origin":4311,"position":0},"title":"lparallel: A Parallel Programming Library","author":"admin","date":"April 26, 2021","format":false,"excerpt":"You may recall that in the last article I had reviewed the book \"Algorithms in Lisp\"\u00a0by Vsevolod Domkin. There was a reference to the lparallel\u00a0library in Chapter 15 of the book. That immediately reminded me of the nice discussion of lparallel by Edi Weitz in Chapter 11 of his excellent\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"pmap: Parallel Map","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/pmap-300x208.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/pmap-300x208.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/pmap-300x208.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2084,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/08\/16\/pattern-matching-comparing-elixir-and-mathematica\/","url_meta":{"origin":4311,"position":1},"title":"Pattern Matching: Comparing Elixir and Mathematica","author":"admin","date":"August 16, 2020","format":false,"excerpt":"One of the things I like about Elixir\u00a0is its support for patterns at the core language level, not through library functions as in most other languages. This contributes to writing cleaner code, in my opinion. \u00a0 Another environment that I am familiar with, namely Mathematica, boasts of (arguably) the most\u2026","rel":"","context":"In "Elixir"","block_context":{"text":"Elixir","link":"https:\/\/www.rangakrish.com\/index.php\/category\/elixir\/"},"img":{"alt_text":"Symbolic Expressions","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/08\/pattern-mm.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/08\/pattern-mm.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/08\/pattern-mm.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":3070,"url":"https:\/\/www.rangakrish.com\/index.php\/2023\/04\/02\/building-v-language-dll\/","url_meta":{"origin":4311,"position":2},"title":"Building V Language DLL","author":"admin","date":"April 2, 2023","format":false,"excerpt":"The relatively new V Programming Language (Vlang) boasts of some interesting features such as \u201cfast compilation\u201d and runtime performance \u201cas fast as C\u201d, at the same time being a \u201csimple language\u201d. As I normally do with other languages that I learn and use, I decided to see how easy it\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"V Program","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2023\/04\/V-source-267x300.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2406,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/05\/09\/eager-future2-common-lisp-library\/","url_meta":{"origin":4311,"position":3},"title":"Eager Future2 Common Lisp Library","author":"admin","date":"May 9, 2021","format":false,"excerpt":"Eager Future2 is a Common Lisp library that facilitates parallel computation. It is based on the idea of a \u201cfuture\u201d that acts as a \u201cproxy\u201d for a concurrently computed expression. Unlike the \u201clparallel\u201d library that I had discussed in the last article, this library does not give us control over\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Fibonacci Calculation - 3 Ways","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/05\/Code-232x300.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2765,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/04\/17\/calling-lisp-functions-from-xojo\/","url_meta":{"origin":4311,"position":4},"title":"Calling Lisp Functions from Xojo","author":"admin","date":"April 17, 2022","format":false,"excerpt":"A few days ago, I purchased Xojo Pro commercial license. In case you haven't heard about the product, Xojo\u00a0is a popular cross-platform development tool targeting Desktop, Web and iOS (Android is expected in the near future). It supports an Object-Oriented Basic language. It has been around for over 25 years\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"The Lisp Code","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/04\/LispCode-300x168.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/04\/LispCode-300x168.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/04\/LispCode-300x168.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2377,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/12\/book-review-programming-algorithms-in-lisp\/","url_meta":{"origin":4311,"position":5},"title":"Book Review: Programming Algorithms in Lisp","author":"admin","date":"April 12, 2021","format":false,"excerpt":"Title: Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp Author: Vsevolod Domkin Publisher: Apress Year: 2021 It is only about 5 months since I read and reviewed\u00a0a good book on Lisp written by Micha\u0142 \u201cphoe\u201d Herda. The present book is by Vsevolod Domkin\u00a0and I purchased\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/Book-Cover-209x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/4311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=4311"}],"version-history":[{"count":3,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/4311\/revisions"}],"predecessor-version":[{"id":4318,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/4311\/revisions\/4318"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=4311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=4311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=4311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}