{"id":23420,"date":"2022-11-25T22:37:37","date_gmt":"2022-11-25T17:07:37","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/"},"modified":"2022-11-25T22:37:37","modified_gmt":"2022-11-25T17:07:37","slug":"solved-understanding-recursion-with-the-fibonacci-series","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/","title":{"rendered":"[Solved] Understanding recursion with the Fibonacci Series"},"content":{"rendered":"<p> [ad_1]<br \/>\n<\/p>\n<div id=\"answer-46333422\" class=\"answer js-answer accepted-answer js-accepted-answer\" data-answerid=\"46333422\" data-parentid=\"46333408\" data-score=\"40\" data-position-on-page=\"1\" data-highest-scored=\"1\" data-question-has-accepted-highest-score=\"1\" itemprop=\"acceptedAnswer\" itemscope itemtype=\"https:\/\/schema.org\/Answer\">\n<div class=\"post-layout\">\n<div class=\"votecell post-layout--left\"><\/div>\n<div class=\"answercell post-layout--right\">\n<div class=\"s-prose js-post-body\" itemprop=\"text\">\n<p>When in doubt, just break it down.<\/p>\n<p><a rel=\"nofollow noopener\" target=\"_blank\" href=\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\"><img decoding=\"async\" src=\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\" alt=\"enter image description here\"><\/a><\/p>\n<p>The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you hit the base case (the <code>if<\/code> statements). Now you can carry out all the small computations, and combining the results of those small computations to form a bigger, larger result, until you have your final answer. <\/p>\n<p>Every time a recursive call hits the base case, it will return either 1, or 0, depending on what case was hit. This value will be returned to the previous caller. To understand, consider:<\/p>\n<pre><code>f(1)<sub>3<\/sub> + f(0)<sub>3<\/sub><\/code><\/pre>\n<p>Note here that the subscript represents the depth of the recursion call tree. The call is made by <code>f(2)<sub>2<\/sub><\/code>. <code>f(1)<sub>3<\/sub><\/code> is computed first, and <code>1<\/code> is returned to <code>f(2)<sub>2<\/sub><\/code>. <code>f(0)<sub>3<\/sub><\/code> is then computed, and <code>0<\/code> is returned to <code>f(2)<sub>2<\/sub><\/code>. The two return values are summed, and the result is <code>1<\/code>. <\/p>\n<p><code>f(2)<sub>2<\/sub><\/code> then <em>returns<\/em> <code>1<\/code> to whoever called <em>it<\/em>, which in this case happens to be <code>f(3)<sub>1<\/sub><\/code>. <code>f(3)<sub>1<\/sub><\/code> called <code>f(2)<sub>2<\/sub> + f(1)<sub>2<\/sub><\/code>, meanwhile this other <code>f(1)<sub>2<\/sub><\/code> also returns <code>1<\/code> to <code>f(3)<sub>1<\/sub><\/code>, who now adds that with the result of <code>f(2)<sub>2<\/sub><\/code>, to form <code>2<\/code>. <\/p>\n<p><code>f(3)<sub>1<\/sub><\/code> now passes <code>2<\/code> to <code>f(4)<sub>0<\/sub><\/code>, its caller, which happened to call <code>f(3)<sub>1<\/sub> + f(2)<sub>1<\/sub><\/code> &#8230; and so it goes.<\/p>\n<hr>\n<p>An alternative way of looking at this is to start from the first function call that is actually made: <code>f(4)<sub>0<\/sub><\/code>.<\/p>\n<p><code>f(4)<sub>0<\/sub><\/code> computes <code>f(3)<sub>1<\/sub> + f(2)<sub>1<\/sub><\/code>. But to compute <code>f(3)<sub>1<\/sub><\/code>, it needs to know <code>f(2)<sub>2<\/sub> + f(1)<sub>2<\/sub><\/code>, and similarly, to compute <code>f(2)<sub>1<\/sub><\/code>, it needs to know <code>f(1)<sub>2<\/sub> + f(0)<sub>2<\/sub><\/code>, and so on.<\/p>\n<\/p><\/div>\n<div class=\"mt24\"><\/div>\n<\/div>\n<p>            <span class=\"d-none\" itemprop=\"commentCount\">3<\/span> <\/p><\/div>\n<\/div>\n<p>[ad_2]<\/p>\n<p>solved Understanding recursion with the Fibonacci Series <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[ad_1] When in doubt, just break it down. The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you &#8230; <a title=\"[Solved] Understanding recursion with the Fibonacci Series\" class=\"read-more\" href=\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\" aria-label=\"More on [Solved] Understanding recursion with the Fibonacci Series\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[2803,413,349,494],"class_list":["post-23420","post","type-post","status-publish","format-standard","hentry","category-solved","tag-fibonacci","tag-function","tag-python","tag-recursion"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>[Solved] Understanding recursion with the Fibonacci Series - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Understanding recursion with the Fibonacci Series - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] When in doubt, just break it down. The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-11-25T17:07:37+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Understanding recursion with the Fibonacci Series\",\"datePublished\":\"2022-11-25T17:07:37+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\"},\"wordCount\":260,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\",\"keywords\":[\"fibonacci\",\"function\",\"python\",\"recursion\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\",\"name\":\"[Solved] Understanding recursion with the Fibonacci Series - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\",\"datePublished\":\"2022-11-25T17:07:37+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Understanding recursion with the Fibonacci Series\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Understanding recursion with the Fibonacci Series - JassWeb","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:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Understanding recursion with the Fibonacci Series - JassWeb","og_description":"[ad_1] When in doubt, just break it down. The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/","og_site_name":"JassWeb","article_published_time":"2022-11-25T17:07:37+00:00","og_image":[{"url":"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg","type":"","width":"","height":""}],"author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Understanding recursion with the Fibonacci Series","datePublished":"2022-11-25T17:07:37+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/"},"wordCount":260,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"image":{"@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage"},"thumbnailUrl":"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg","keywords":["fibonacci","function","python","recursion"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/","url":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/","name":"[Solved] Understanding recursion with the Fibonacci Series - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"primaryImageOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage"},"image":{"@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage"},"thumbnailUrl":"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg","datePublished":"2022-11-25T17:07:37+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#primaryimage","url":"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/uploads\/2022\/11\/Solved-Understanding-recursion-with-the-Fibonacci-Series.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-understanding-recursion-with-the-fibonacci-series\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Understanding recursion with the Fibonacci Series"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/23420","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=23420"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/23420\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=23420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=23420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=23420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}