{"id":7358,"date":"2022-08-04T14:08:22","date_gmt":"2022-08-04T08:38:22","guid":{"rendered":"https:\/\/www.innovationm.com\/blog\/?p=7358"},"modified":"2022-08-04T14:08:22","modified_gmt":"2022-08-04T08:38:22","slug":"recursion-vs-dynamic-programming-fibonacci","status":"publish","type":"post","link":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/","title":{"rendered":"Recursion vs Dynamic Programming \u2014 Fibonacci"},"content":{"rendered":"

Introduction of Recursion and Dynamic Programming:<\/strong><\/p>\n

\"\"<\/p>\n

Recursion <\/strong>is the process in which a function calls itself until the base cases are reached. And during the process, complex situations will be traced recursively and become simpler and simpler. The whole structure of the process is tree-like. Recursion does not store any value <\/strong>until reaching the final stage(base case).<\/p>\n

And Dynamic Programming<\/strong> is mainly an optimization compared to simple recursion. The main idea is to decompose the original question into repeatable patterns and then store the results as many sub-answers<\/strong>. Therefore, we do not have to re-compute<\/strong> the pre-step answers when needed later. In terms of big O, this optimization method generally reduces time complexities from exponential to polynomial.<\/p>\n

\"\"<\/p>\n

How to write a recursion\/dynamic programming script?<\/strong><\/p>\n

Dynamic Programming and Recursion are very similar-<\/em><\/p>\n

    \n
  1. Both recursion and dynamic programming are starting with the base case where we initialize the start.<\/li>\n
  2. After we wrote the base case, we will try to find any patterns followed by the problem\u2019s logic flow. Once we find it, we are basically done.<\/li>\n
  3. The main difference is that, for recursion, we do not store any intermediate values<\/strong> whereas dynamic programming does utilize that<\/li>\n<\/ol>\n

    Problem Statement:<\/strong><\/p>\n

    \"\"<\/p>\n

    Example: Leetcode 509. Fibonacci Number<\/strong><\/p>\n

    Problem Prompt-<\/strong><\/p>\n

    The Fibonacci numbers, commonly denoted <\/em>F(n)<\/em> form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from <\/em>0<\/em> and <\/em>1<\/em>. That is,<\/em><\/p>\n

    F[0] = 0 as the first number\r\n\r\nF[1] = 1 as our second number\r\n\r\nAnd the number after that is easy to compute:\r\n\r\nF[n] = F[n-1] + F[n-2]<\/pre>\n
    Examples-<\/strong><\/p>\n
    \"\"<\/p>\n
    How could we find F[n] with a given n?<\/em><\/strong><\/p>\n
    \u00a0Examples-<\/strong><\/p>\n
    If this is the very first time heard something called Fibonacci Number, do not worry, here are some easy examples to understand the question:<\/p>\n
    Given n = 2, F[2] = F[1] + F[0] = 0 + 1 = 1\r\n\r\nGiven n = 3, F[3] = F[2] + F[1] = 1+ 2= 3<\/pre>\n
    \"\"<\/p>\n
    Fibonacci Tree with recursive Approach leads to O(2^n) time complexity, but this is too bad for larger problems this is okay for small problems.<\/em><\/p>\n
    To Optimize the time complexity of Fibonacci recursive problems we use memoization and dynamic programming.<\/em><\/p>\n
    \"\"<\/p>\n
    The Following Tree is having multiple same recursive calls so that\u2019s why we optimize the following approach using memoization and dynamic programming where we need to remove the recursive calls and store them in an array.<\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Introduction of Recursion and Dynamic Programming: Recursion is the process in which a function calls itself until the base cases are reached. And during the process, complex situations will be traced recursively and become simpler and simpler. The whole structure of the process is tree-like. Recursion does not store any value until reaching the final […]<\/p>\n","protected":false},"author":1,"featured_media":7365,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[256,360],"tags":[722,723,792,790,224,346,791],"class_list":["post-7358","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java-application","category-javascript","tag-blog","tag-blogging","tag-dynamic-programming","tag-fibonacci","tag-java","tag-javascript","tag-recursion"],"yoast_head":"\nRecursion vs Dynamic Programming \u2014 Fibonacci - InnovationM - Blog<\/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:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Recursion vs Dynamic Programming \u2014 Fibonacci - InnovationM - Blog\" \/>\n<meta property=\"og:description\" content=\"Introduction of Recursion and Dynamic Programming: Recursion is the process in which a function calls itself until the base cases are reached. And during the process, complex situations will be traced recursively and become simpler and simpler. The whole structure of the process is tree-like. Recursion does not store any value until reaching the final […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/\" \/>\n<meta property=\"og:site_name\" content=\"InnovationM - Blog\" \/>\n<meta property=\"article:published_time\" content=\"2022-08-04T08:38:22+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2022\/08\/Recursion-vs-Dynamic-Programming-Fibonacci.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1689\" \/>\n\t<meta property=\"og:image:height\" content=\"950\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"InnovationM Admin\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"InnovationM Admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/\"},\"author\":{\"name\":\"InnovationM Admin\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#\\\/schema\\\/person\\\/a831bf4602d69d1fa452e3de0c8862ed\"},\"headline\":\"Recursion vs Dynamic Programming \u2014 Fibonacci\",\"datePublished\":\"2022-08-04T08:38:22+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/\"},\"wordCount\":355,\"commentCount\":0,\"image\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/08\\\/Recursion-vs-Dynamic-Programming-Fibonacci.png\",\"keywords\":[\"blog\",\"blogging\",\"dynamic programming\",\"fibonacci\",\"java\",\"JavaScript\",\"recursion\"],\"articleSection\":[\"Java Application\",\"JavaScript\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/\",\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/\",\"name\":\"Recursion vs Dynamic Programming \u2014 Fibonacci - InnovationM - Blog\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/08\\\/Recursion-vs-Dynamic-Programming-Fibonacci.png\",\"datePublished\":\"2022-08-04T08:38:22+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#\\\/schema\\\/person\\\/a831bf4602d69d1fa452e3de0c8862ed\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/08\\\/Recursion-vs-Dynamic-Programming-Fibonacci.png\",\"contentUrl\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/08\\\/Recursion-vs-Dynamic-Programming-Fibonacci.png\",\"width\":1689,\"height\":950},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/recursion-vs-dynamic-programming-fibonacci\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Recursion vs Dynamic Programming \u2014 Fibonacci\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/\",\"name\":\"InnovationM - Blog\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#\\\/schema\\\/person\\\/a831bf4602d69d1fa452e3de0c8862ed\",\"name\":\"InnovationM Admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g\",\"caption\":\"InnovationM Admin\"},\"sameAs\":[\"http:\\\/\\\/www.innovationm.com\\\/\"],\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/author\\\/innovationmadmin\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Recursion vs Dynamic Programming \u2014 Fibonacci - InnovationM - Blog","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:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/","og_locale":"en_US","og_type":"article","og_title":"Recursion vs Dynamic Programming \u2014 Fibonacci - InnovationM - Blog","og_description":"Introduction of Recursion and Dynamic Programming: Recursion is the process in which a function calls itself until the base cases are reached. And during the process, complex situations will be traced recursively and become simpler and simpler. The whole structure of the process is tree-like. Recursion does not store any value until reaching the final […]","og_url":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/","og_site_name":"InnovationM - Blog","article_published_time":"2022-08-04T08:38:22+00:00","og_image":[{"width":1689,"height":950,"url":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2022\/08\/Recursion-vs-Dynamic-Programming-Fibonacci.png","type":"image\/png"}],"author":"InnovationM Admin","twitter_misc":{"Written by":"InnovationM Admin","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#article","isPartOf":{"@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/"},"author":{"name":"InnovationM Admin","@id":"https:\/\/www.innovationm.com\/blog\/#\/schema\/person\/a831bf4602d69d1fa452e3de0c8862ed"},"headline":"Recursion vs Dynamic Programming \u2014 Fibonacci","datePublished":"2022-08-04T08:38:22+00:00","mainEntityOfPage":{"@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/"},"wordCount":355,"commentCount":0,"image":{"@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#primaryimage"},"thumbnailUrl":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2022\/08\/Recursion-vs-Dynamic-Programming-Fibonacci.png","keywords":["blog","blogging","dynamic programming","fibonacci","java","JavaScript","recursion"],"articleSection":["Java Application","JavaScript"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/","url":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/","name":"Recursion vs Dynamic Programming \u2014 Fibonacci - InnovationM - Blog","isPartOf":{"@id":"https:\/\/www.innovationm.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#primaryimage"},"image":{"@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#primaryimage"},"thumbnailUrl":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2022\/08\/Recursion-vs-Dynamic-Programming-Fibonacci.png","datePublished":"2022-08-04T08:38:22+00:00","author":{"@id":"https:\/\/www.innovationm.com\/blog\/#\/schema\/person\/a831bf4602d69d1fa452e3de0c8862ed"},"breadcrumb":{"@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#primaryimage","url":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2022\/08\/Recursion-vs-Dynamic-Programming-Fibonacci.png","contentUrl":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2022\/08\/Recursion-vs-Dynamic-Programming-Fibonacci.png","width":1689,"height":950},{"@type":"BreadcrumbList","@id":"https:\/\/www.innovationm.com\/blog\/recursion-vs-dynamic-programming-fibonacci\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.innovationm.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Recursion vs Dynamic Programming \u2014 Fibonacci"}]},{"@type":"WebSite","@id":"https:\/\/www.innovationm.com\/blog\/#website","url":"https:\/\/www.innovationm.com\/blog\/","name":"InnovationM - Blog","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.innovationm.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.innovationm.com\/blog\/#\/schema\/person\/a831bf4602d69d1fa452e3de0c8862ed","name":"InnovationM Admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g","caption":"InnovationM Admin"},"sameAs":["http:\/\/www.innovationm.com\/"],"url":"https:\/\/www.innovationm.com\/blog\/author\/innovationmadmin\/"}]}},"_links":{"self":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/posts\/7358","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/comments?post=7358"}],"version-history":[{"count":0,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/posts\/7358\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/media\/7365"}],"wp:attachment":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/media?parent=7358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/categories?post=7358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/tags?post=7358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}