{"id":123293,"date":"2024-02-13T18:00:58","date_gmt":"2024-02-13T12:30:58","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=123293"},"modified":"2024-03-09T14:08:39","modified_gmt":"2024-03-09T08:38:39","slug":"fibonacci-series-in-c-using-recursion","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/","title":{"rendered":"Fibonacci Series in C using Recursion"},"content":{"rendered":"<p>Each number in the Fibonacci series is calculated by adding the two preceding integers. This series was first described by Italian mathematician Fibonacci in the 13th century and appears often in mathematics and nature.<\/p>\n<p>In computer science, calculating the Fibonacci numbers recursively is a common exercise used to teach recursion. This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.<\/p>\n<h2>Fibonacci Series in C Explained<\/h2>\n<p><strong>Each integer in the Fibonacci series after 0 and 1 is the sum of the two before it:<\/strong><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">F(0) = 0 \r\nF(1) = 1\r\nF(n) = F(n-1) + F(n-2), n &gt; 1<\/pre>\n<p><strong>The first few Fibonacci numbers are:<\/strong><\/p>\n<p>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89\u2026<\/p>\n<p>This sequence exhibits a certain pattern and mathematical properties that make it interesting for analysis.<\/p>\n<h3>Recursion Fundamentals in C<\/h3>\n<p>Recursion is a technique in programming where a function calls itself to repeat a computational procedure. <strong>Recursion requires:<\/strong><\/p>\n<ul>\n<li style=\"list-style-type: none\">\n<ul>\n<li><strong>Base case(s) &#8211;<\/strong> the condition where the recursion stops<\/li>\n<li><strong>Recursive call(s) &#8211;<\/strong> the function calling itself with different inputs<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><strong>For example, a recursive function to calculate factorial:<\/strong><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">int factorial(int n) {\r\n  if (n == 0) { \/\/ base case \r\n    return 1;\r\n  }\r\n  return n * factorial(n-1); \/\/ recursive call\r\n}<\/pre>\n<h3>Recursive Approach to Fibonacci in C<\/h3>\n<p>The Fibonacci sequence can be calculated using recursion by breaking down the problem into smaller subproblems using the recursive definition of Fibonacci numbers.<\/p>\n<p><strong>The steps are:<\/strong><\/p>\n<h4>1. Base cases:<\/h4>\n<ul>\n<li style=\"list-style-type: none\">\n<ul>\n<li>F(0) = 0<\/li>\n<li>F(1) = 1<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h4>2. Recursive step:<\/h4>\n<ul>\n<li style=\"list-style-type: none\">\n<ul>\n<li>To find F(n), recursively find F(n-1) and F(n-2)<\/li>\n<li>Then compute F(n) as F(n-1) + F(n-2)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>This way, larger Fibonacci numbers are solved by recursively reducing the problem to smaller Fibonacci numbers until a base case is reached.<\/p>\n<p>The base cases provide starting values to build up the solution. The recursive step uses previously solved subproblems to solve larger problems.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2024\/02\/recursive-step.webp\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-134527 size-full\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2024\/02\/recursive-step.webp\" alt=\"recursive step\" width=\"600\" height=\"287\" \/><\/a><\/p>\n<p>The computation of fib(5) can be understood as a recursive breakdown. Initially, we divide it into two sub-problems: fib(4) and fib(3).<\/p>\n<p>When we delve into fib(4), it further disassembles into fib(3) and fib(2). Similarly, fib(3) splits into fib(2) and fib(1). This recursive partitioning continues until we reach the fundamental cases of fib(1) with a value of 1 and fib(0) with a value of 0 in both branches.<\/p>\n<p>Subsequently, each computed value is propagated back up the chain to its parent caller. They accumulate these returned values to determine their own result. This iterative summation continues throughout the entire process until we ultimately obtain the final result for fib(5).<\/p>\n<h3>C Code Implementation<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\r\n\r\nint fib(int n) {\r\n  if (n == 0) { \r\n    return 0;\r\n  }\r\n  if (n == 1) {\r\n    return 1;\r\n  }\r\n  return fib(n-1) + fib(n-2); \r\n}\r\n\r\nint main() {\r\n  int n = 6;\r\n  printf(\"Fibonacci number %d is %d\", n, fib(n));\r\n  return 0;\r\n}<\/pre>\n<p>The given C code calculates the 6th Fibonacci number using a recursive function and then prints the result.<\/p>\n<p><strong>Let&#8217;s walk through the code and determine the output:<\/strong><\/p>\n<p>1. The fib function is defined to calculate Fibonacci numbers using recursion.<\/p>\n<p>2. In the main function, the variable n is set to 6.<\/p>\n<p>3. The printf statement prints the 6th Fibonacci number, calculated by calling fib(6).<\/p>\n<p><strong>Now, let&#8217;s calculate the Fibonacci number for n = 6 using the fib function:<\/strong><\/p>\n<ul>\n<li>fib(6) calls fib(5) and fib(4).<\/li>\n<li>fib(5) calls fib(4) and fib(3).<\/li>\n<li>fib(4) calls fib(3) and fib(2).<\/li>\n<li>fib(3) calls fib(2) and fib(1).<\/li>\n<li>fib(2) calls fib(1) and fib(0).<\/li>\n<li>fib(1) returns 1.<\/li>\n<li>fib(0) returns 0.<\/li>\n<li>fib(2) returns 1 (the sum of fib(1) and fib(0)).<\/li>\n<li>fib(3) returns 2 (the sum of fib(2) and fib(1)).<\/li>\n<li>fib(4) returns 3 (the sum of fib(3) and fib(2)).<\/li>\n<li>fib(5) returns 5 (the sum of fib(4) and fib(3)).<\/li>\n<li>Finally, fib(6) returns 8 (the sum of fib(5) and fib(4)).<\/li>\n<\/ul>\n<p><strong>Output:<\/strong><br \/>\nFibonacci number 6 is 8<\/p>\n<h3>Comparison with Other Approaches in C<\/h3>\n<h4>1. Iterative approach<\/h4>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">int fib(int n) {\r\n  int a = 0, b = 1, c, i;\r\n  if (n == 0) {\r\n    return a;\r\n  }\r\n  for (i = 2; i &lt;= n; i++) {\r\n    c = a + b;\r\n    a = b;\r\n    b = c;\r\n  }\r\n  return b;\r\n}<\/pre>\n<p>The recursive approach is simpler and elegant but less efficient than the iterative solution. Recursion provides a natural way to express the Fibonacci definition. However, iteration avoids call stack overflows for large n.<\/p>\n<h4>2. Fibonacci Matrix Method<\/h4>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n\r\n\/\/ Define a matrix structure\r\ntypedef struct {\r\n    long long int data[2][2];\r\n} Matrix;\r\n\r\n\/\/ Initialize the identity matrix\r\nMatrix identityMatrix() {\r\n    Matrix mat;\r\n    mat.data[0][0] = 1;\r\n    mat.data[0][1] = 1;\r\n    mat.data[1][0] = 1;\r\n    mat.data[1][1] = 0;\r\n    return mat;\r\n}<\/pre>\n<p><strong>Multiply two matrices<\/strong><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">Matrix multiply(Matrix a, Matrix b) {\r\n    Matrix result;\r\n    int i, j, k;\r\n    for (i = 0; i &lt; 2; i++) {\r\n        for (j = 0; j &lt; 2; j++) {\r\n            result.data[i][j] = 0;\r\n            for (k = 0; k &lt; 2; k++) {\r\n                result.data[i][j] += a.data[i][k] * b.data[k][j];\r\n            }\r\n        }\r\n    }\r\n    return result;\r\n}<\/pre>\n<p><strong>Calculate the Nth power of a matrix<\/strong><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">Matrix matrixPower(Matrix mat, int n) {\r\n    Matrix result = identityMatrix();\r\n    while (n &gt; 0) {\r\n        if (n % 2 == 1) {\r\n            result = multiply(result, mat);\r\n        }\r\n        mat = multiply(mat, mat);\r\n        n \/= 2;\r\n    }\r\n    return result;\r\n}<\/pre>\n<p><strong>Find the Nth Fibonacci number using the matrix approach<\/strong><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">long long int nthFibonacci(int n) {\r\n    if (n &lt;= 0) return 0;\r\n    Matrix fibMatrix = matrixPower(identityMatrix(), n - 1);\r\n    return fibMatrix.data[0][0];\r\n}\r\n\r\nint main() {\r\n    int n;\r\n    printf(\"Enter the value of N: \");\r\n    scanf(\"%d\", &amp;n);\r\n\r\n    long long int result = nthFibonacci(n);\r\n    printf(\"The %dth Fibonacci number is: %lld\\n\", n, result);\r\n\r\n    return 0;\r\n}<\/pre>\n<h3>Conclusion<\/h3>\n<p>This article covered a recursive algorithm for generating Fibonacci numbers and its implementation in C. Recursion in C is an important concept in programming. The Fibonacci sequence presents a good introductory example of applying recursion principles. Further exploration of topics like recursion runtime analysis and optimizations can build stronger foundations in computer science.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Each number in the Fibonacci series is calculated by adding the two preceding integers. This series was first described by Italian mathematician Fibonacci in the 13th century and appears often in mathematics and nature.&#46;&#46;&#46;<\/p>\n","protected":false},"author":86671,"featured_media":123821,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19488],"tags":[23914,29133,20192,28020,29567],"class_list":["post-123293","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-programming","tag-c-programming","tag-c-tutorials","tag-fibonacci-series-in-c","tag-fibonacci-series-in-c-using-recursion","tag-fibonacci-series-using-recursion-in-c"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Fibonacci Series in C using Recursion - DataFlair<\/title>\n<meta name=\"description\" content=\"This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Fibonacci Series in C using Recursion - DataFlair\" \/>\n<meta property=\"og:description\" content=\"This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2024-02-13T12:30:58+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-03-09T08:38:39+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/11\/fibbonacci-series-using-recursion-in-c.webp\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/webp\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Fibonacci Series in C using Recursion - DataFlair","description":"This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/","og_locale":"en_US","og_type":"article","og_title":"Fibonacci Series in C using Recursion - DataFlair","og_description":"This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.","og_url":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2024-02-13T12:30:58+00:00","article_modified_time":"2024-03-09T08:38:39+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/11\/fibbonacci-series-using-recursion-in-c.webp","type":"image\/webp"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/0e594f928e31fc96628ac40f6ae74f49"},"headline":"Fibonacci Series in C using Recursion","datePublished":"2024-02-13T12:30:58+00:00","dateModified":"2024-03-09T08:38:39+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/"},"wordCount":643,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/11\/fibbonacci-series-using-recursion-in-c.webp","keywords":["c programming","c tutorials","Fibonacci series in C","fibonacci series in c using recursion","fibonacci series using recursion in c"],"articleSection":["C Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/","url":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/","name":"Fibonacci Series in C using Recursion - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/11\/fibbonacci-series-using-recursion-in-c.webp","datePublished":"2024-02-13T12:30:58+00:00","dateModified":"2024-03-09T08:38:39+00:00","description":"This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/11\/fibbonacci-series-using-recursion-in-c.webp","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2023\/11\/fibbonacci-series-using-recursion-in-c.webp","width":1200,"height":628,"caption":"fibbonacci series using recursion in c"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/fibonacci-series-in-c-using-recursion\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"C Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/c-programming\/"},{"@type":"ListItem","position":3,"name":"Fibonacci Series in C using Recursion"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/0e594f928e31fc96628ac40f6ae74f49","name":"TechVidvan Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/c89190da3d4010c71ba476b618ab10fdc2335c82cdfa0ad5002d98d0f2473444?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c89190da3d4010c71ba476b618ab10fdc2335c82cdfa0ad5002d98d0f2473444?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/c89190da3d4010c71ba476b618ab10fdc2335c82cdfa0ad5002d98d0f2473444?s=96&d=mm&r=g","caption":"TechVidvan Team"},"description":"TechVidvan Team provides high-quality content &amp; courses on AI, ML, Data Science, Data Engineering, Data Analytics, programming, Python, DSA, Android, Flutter, full stack web dev, MERN, and many latest technology.","url":"https:\/\/data-flair.training\/blogs\/author\/test001\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/123293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/86671"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=123293"}],"version-history":[{"count":9,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/123293\/revisions"}],"predecessor-version":[{"id":134529,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/123293\/revisions\/134529"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/123821"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=123293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=123293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=123293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}