{"id":6398,"date":"2025-06-04T20:25:29","date_gmt":"2025-06-04T14:55:29","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=6398"},"modified":"2025-06-04T20:26:12","modified_gmt":"2025-06-04T14:56:12","slug":"fibonacci-number-using-recursion","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/fibonacci-number-using-recursion\/","title":{"rendered":"Fibonacci Number using Recursion"},"content":{"rendered":"\n<!-- Prism.js CSS and JS -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.css\" rel=\"stylesheet\" \/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_code-tabs-container {\n    font-family: \"Segoe UI\", sans-serif !important;\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    border: 1px solid #ddd !important;\n    border-radius: 8px !important;\n    overflow: hidden !important;\n    background-color: white !important;\n}\n\n.wp_blog_code-tabs-header {\n    background: #f7f7f7 !important;\n    display: flex !important;\n    border-bottom: 1px solid #ddd !important;\n}\n\n.wp_blog_code-tab-button {\n    flex: 1 !important;\n    padding: 10px 15px !important;\n    border: none !important;\n    background: transparent !important;\n    cursor: pointer !important;\n    font-weight: bold !important;\n    transition: background 0.2s !important;\n    color: #242B33 !important;\n}\n\n.wp_blog_code-tab-button.active {\n    background: white !important;\n    border-bottom: 3px solid #0073aa !important;\n}\n\n.wp_blog_code-tab-content {\n    display: none !important;\n    padding: 20px !important;\n    background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content > pre {\n    background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content.active {\n    display: block !important;\n}\n\n.wp_blog_code-tab-content pre {\n    margin: 0 !important;\n    overflow-x: auto !important;\n}\n\n.wp_blog_explanation {\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    font-family: \"Segoe UI\", sans-serif !important;\n    line-height: 1.6 !important;\n    background: white !important;\n    color: black !important;\n    padding: 1rem !important;\n    border-radius: 8px !important;\n}\n\n.wp_blog_explanation h2 {\n    color: #0073aa !important;\n    font-size: 1.5rem !important;\n    margin-bottom: 0.5rem !important;\n}\n\n.wp_blog_explanation code {\n    background: #f1f1f1 !important;\n    padding: 2px 6px !important;\n    border-radius: 4px !important;\n    font-family: monospace !important;\n}\n\n.wp_blog_explanation h1,\n.wp_blog_explanation h2,\n.wp_blog_explanation h3,\n.wp_blog_explanation h4,\n.wp_blog_explanation h5,\n.wp_blog_explanation h6,\n.wp_blog_explanation p {\n    margin-top: 10px !important;\n    margin-bottom: 10px !important;\n}\n<\/style>\n\n<!-- \u2705 START: Blog Explanation -->\n<div class=\"wp_blog_explanation\">\n  <h2>What is a Fibonacci Number?<\/h2>\n  <p>The Fibonacci sequence is a famous mathematical series in which each number is the sum of the two preceding ones. It\u2019s defined by the recurrence relation:<\/p>\n  <pre><code>F(0) = 0  \nF(1) = 1  \nF(n) = F(n-1) + F(n-2)  for n > 1<\/code><\/pre>\n  <p>This generates a series like:<\/p>\n  <pre><code>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...<\/code><\/pre>\n  <p>Each number is the sum of the two before it.<\/p>\n  <p>This sequence appears frequently in nature (e.g., flower petals, pine cones, and spiral shells), in algorithms (like dynamic programming), and even in computer science problems related to recursion, time complexity, and optimization.<\/p>\n\n  <h2>Approach: Recursion<\/h2>\n  <p>Recursion is a technique where a function solves a problem by calling itself on smaller sub-problems.<\/p>\n  <p>In the context of Fibonacci:<\/p>\n  <ul>\n    <li>To compute fib(n), we:<\/li>\n    <li>Ask: &#8220;What is fib(n-1)?&#8221;<\/li>\n    <li>Ask: &#8220;What is fib(n-2)?&#8221;<\/li>\n    <li>Return the sum of the two: fib(n) = fib(n-1) + fib(n-2)<\/li>\n  <\/ul>\n  <p>This continues until we reach the base cases:<\/p>\n  <ul>\n    <li>If n == 0, return 0<\/li>\n    <li>If n == 1, return 1<\/li>\n  <\/ul>\n\n  <h2>Time &#038; Space Complexity<\/h2>\n  <ul>\n    <li><strong>Time Complexity:<\/strong> O(2^n)<br>This is because each function call makes 2 recursive calls, leading to a binary tree of calls.<\/li>\n    <li>For large n, this becomes very inefficient, as many subproblems are solved repeatedly.<\/li>\n    <li><strong>Space Complexity:<\/strong> O(n)<br>Although the number of calls is exponential, the maximum call depth is n.<\/li>\n    <li>So, the space used on the call stack is linear in the worst case.<\/li>\n  <\/ul>\n\n  <h2>Sample Outputs<\/h2>\n  <table>\n    <tr><th>Input n<\/th><th>Output fib(n)<\/th><\/tr>\n    <tr><td>0<\/td><td>0<\/td><\/tr>\n    <tr><td>1<\/td><td>1<\/td><\/tr>\n    <tr><td>2<\/td><td>1<\/td><\/tr>\n    <tr><td>3<\/td><td>2<\/td><\/tr>\n    <tr><td>5<\/td><td>5<\/td><\/tr>\n    <tr><td>6<\/td><td>8<\/td><\/tr>\n    <tr><td>7<\/td><td>13<\/td><\/tr>\n    <tr><td>10<\/td><td>55<\/td><\/tr>\n  <\/table>\n<\/div>\n\n<div class=\"wp_blog_code-tabs-container\">\n  <div class=\"wp_blog_code-tabs-header\">\n    <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n    <pre><code class=\"language-javascript\">var fib = function(n) {\n    if (n <= 1)\n        return n;\n    return fib(n - 1) + fib(n - 2);\n};<\/code><\/pre>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n    <pre><code class=\"language-c\">int fib(int n) {\n    if (n <= 1)\n        return n;\n    return fib(n - 1) + fib(n - 2);\n}<\/code><\/pre>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n    <pre><code class=\"language-cpp\">class Solution {\npublic:\n    int fib(int n) {\n        if (n <= 1)\n            return n;\n        return fib(n - 1) + fib(n - 2);\n    }\n};<\/code><\/pre>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n    <pre><code class=\"language-java\">class Solution {\n    public int fib(int n) {\n        if (n <= 1)\n            return n;\n        return fib(n - 1) + fib(n - 2);\n    }\n}<\/code><\/pre>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n    <pre><code class=\"language-python\">class Solution(object):\n    def fib(self, n):\n        \"\"\"\n        :type n: int\n        :rtype: int\n        \"\"\"\n        if n <= 1:\n            return n\n        return self.fib(n - 1) + self.fib(n - 2)<\/code><\/pre>\n  <\/div>\n\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n    <pre><code class=\"language-csharp\">public class Solution {\n    public int Fib(int n) {\n        if (n <= 1)\n            return n;\n        return Fib(n - 1) + Fib(n - 2);\n    }\n}<\/code><\/pre>\n  <\/div>\n<\/div>\n\n<!-- \u2705 JS Tab Switch Logic -->\n<script>\ndocument.addEventListener('DOMContentLoaded', function () {\n    const buttons = document.querySelectorAll('.wp_blog_code-tab-button');\n    const contents = document.querySelectorAll('.wp_blog_code-tab-content');\n    buttons.forEach(button => {\n        button.addEventListener('click', () => {\n            const lang = button.getAttribute('data-lang');\n            buttons.forEach(btn => btn.classList.remove('active'));\n            button.classList.add('active');\n            contents.forEach(content => {\n                content.classList.toggle('active', content.getAttribute('data-lang') === lang);\n            });\n        });\n    });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>What is a Fibonacci Number? The Fibonacci sequence is a famous mathematical series in which each number is the sum of the two preceding ones. It\u2019s defined by the recurrence relation: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n > 1 This generates a series like: 0, 1, 1, 2,<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[260,175,811,810,174,172,173],"tags":[],"class_list":{"0":"post-6398","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-c-c-plus-plus","7":"category-cplusplus","8":"category-data-structures-and-algorithms","9":"category-dsa","10":"category-java","11":"category-javascript","12":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6398","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=6398"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6398\/revisions"}],"predecessor-version":[{"id":6399,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6398\/revisions\/6399"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=6398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=6398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=6398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}