{"id":77820,"date":"2020-04-01T13:56:33","date_gmt":"2020-04-01T08:26:33","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=77820"},"modified":"2020-04-01T13:56:33","modified_gmt":"2020-04-01T08:26:33","slug":"python-recursion","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/","title":{"rendered":"Python Recursion – A programmer’s most important weapon"},"content":{"rendered":"

Coders often joke, \u201cIn order to understand recursion, you must first understand recursion\u201d<\/strong>.<\/p>\n

Funny, right?<\/p>\n

Well if you didn\u2019t find it funny, scroll back up after reading this entire article on Python Recursion<\/strong> and we know you will like it for sure.<\/p>\n

And if you still don\u2019t like it, I have another one for you!<\/p>\n

\"\"<\/a><\/p>\n

What is Python Recursion?<\/h3>\n

Recursion<\/strong> occurs when a function<\/strong> or algorithm<\/strong> calls itself<\/strong>. It is a problem-solving<\/strong> method that involves repetitive<\/strong> breaking down<\/strong> of a problem<\/strong> into a smaller instance<\/strong> of the same problem<\/strong>. We keep breaking down until we reach a problem that is small enough<\/strong> to be solved easily<\/strong>.<\/p>\n

We usually implement recursion<\/strong> through a recursive function<\/strong>.<\/p>\n

Let\u2019s learn the concept of recursion<\/strong> using the classic example<\/strong> of finding factorial<\/strong> of a number<\/strong>.<\/p>\n

Factorial<\/strong> of a number<\/strong> is the product<\/strong> of all integers<\/strong> which are greater than 1<\/strong> and less than<\/strong> or equal to<\/strong> that number<\/strong>.<\/p>\n

For instance, the factorial<\/strong> of 4 is 4 * 3 * 2 * 1<\/strong>.<\/p>\n

So basically, for any non-negative integer N<\/strong>, the factorial of N = N * factorial of (N – 1)<\/strong><\/p>\n

Python Recursive Function<\/h3>\n

\"\"<\/a><\/p>\n

A recursive function<\/strong> is one that invokes itself<\/strong> as a part of its execution<\/strong>.<\/p>\n

So if we have a function for calculating<\/strong> the factorial of a number<\/strong>, say factorial(n)<\/strong>, based on the above discussion we can say,<\/p>\n

factorial(n) = n * factorial(n – 1)<\/strong><\/p>\n

Cases in Python Recursive Function<\/h4>\n
    \n
  • The base case,<\/strong> which when satisfied, will terminate<\/strong> the recursive process<\/strong>. This is also known as the \u201cexit condition\u201d<\/strong>.<\/li>\n
  • The recursive case,<\/strong> which is where the recursion<\/strong> will actually occur<\/strong>. That means this is where the function<\/strong> will call itself<\/strong>.<\/li>\n<\/ul>\n

    Finally, let\u2019s put our recursive function for calculating the factorial of a number into code:<\/strong><\/p>\n

    def factorial(n):\n    # base case\n    if n == 1:\n        return 1\n\n    # recursive case\n    else:\n        return n * factorial(n-1)<\/pre>\n
    Run this code and in the Python shell call the function:<\/strong><\/p>\n
    >>> factorial(10)\n3628800\n>>> factorial(5)\n120\n<\/pre>\n
    How does Recursion work in Python<\/strong>?<\/h3>\n
    To get a full understanding of the working process<\/strong> of recursion<\/strong>, we first need to learn about call stack<\/strong>.<\/p>\n
      \n
    • When you call a function<\/strong>, the system sets aside space<\/strong> in the memory<\/strong> for that function<\/strong> to do its work<\/strong>.<\/li>\n
    • Such chunks of memory<\/strong> are called stack frames<\/strong> or function frames<\/strong>.<\/li>\n
    • More than one function\u2019s stack frame<\/strong> may exist in the memory<\/strong> at a given time.<\/li>\n
    • We know that a function has the ability to call another function<\/strong>.<\/li>\n
    • So suppose start()<\/strong> calls move()<\/strong>, which then calls direction()<\/strong>, all 3 functions<\/strong> have open frames<\/strong> in the memory<\/strong>.<\/li>\n
    • But only the function<\/strong> which is called recently<\/strong> has an active frame<\/strong>.<\/li>\n<\/ul>\n
      These frames are arranged<\/strong> in a stack<\/strong>, called the \u2018call stack\u2019<\/strong>. The frame for the most recently called function<\/strong> is always on the top of the stack<\/strong>.<\/p>\n
      When a new function<\/strong> is called<\/strong>, a new frame<\/strong> is pushed<\/strong> onto the top of the stack<\/strong> and becomes the active frame<\/strong>. When a function finishes its work, its frame<\/strong> is popped<\/strong> off<\/strong> from the stack<\/strong> and the frame<\/strong> immediately below becomes<\/strong> the active frame<\/strong>. This active function<\/strong> picks up immediately where it left off.<\/p>\n
      When a function calls another function<\/strong>, the caller function<\/strong> is set on hold<\/strong> and the called function becomes active<\/strong>. Now the frame below<\/strong> this active frame<\/strong> has to wait until<\/strong> it again becomes active<\/strong> and resumes its work<\/strong>.<\/p>\n
      So recalling our factorial code<\/strong>, let\u2019s understand how factorial of 5<\/strong> is calculated.<\/p>\n
      Our factorial(n) function states<\/strong> that, if n<\/strong> is 1<\/strong>, the function returns 1<\/strong>. Otherwise, the function returns n * factorial(n – 1)<\/strong>.<\/p>\n
      So if we call factorial(5)<\/strong> it will in turn call factorial(4)<\/strong>, which will call factorial(3)<\/strong>, which calls factorial(2)<\/strong> and at last we reach factorial(1)<\/strong>.<\/p>\n
      The functions then pop off<\/strong> from the stack one<\/strong> by one as follows:<\/p>\n
      1. factorial(1)<\/strong> returns 1 to the frame of factorial(2)<\/strong> and pops off.<\/p>\n
      2. factorial(2)<\/strong> then pops off after returning 2*1<\/strong> to the frame of factorial(3)<\/strong>.<\/p>\n
      3. factorial(3)<\/strong> then returns 3*2*1<\/strong> to the factorial(4)<\/strong> frame.<\/p>\n
      4. factorial(4)<\/strong> returns 4*3*2*1<\/strong> to the frame of factorial(5)<\/strong><\/p>\n
      5. And lastly, factorial(5)<\/strong> returns 5*4*3*2*1<\/strong> which equates to 120<\/strong>.<\/p>\n
      Summary<\/h3>\n
      That was all for Python Recursion<\/strong>.<\/p>\n
      In this article, our aim was to make you understand how to implement recursion<\/strong> in python<\/strong>. And now that you have also learned what actually happens behind the scenes of recursion<\/strong>, I hope you will get that joke we mentioned earlier in the introduction of this article.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Coders often joke, \u201cIn order to understand recursion, you must first understand recursion\u201d. Funny, right? Well if you didn\u2019t find it funny, scroll back up after reading this entire article on Python Recursion and...<\/p>\n","protected":false},"author":1,"featured_media":77871,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1053],"tags":[2236,2237,2238,2239,2240,1328,2241],"class_list":["post-77820","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-python","tag-cases-in-python-recursive-function","tag-how-python-recursive-work","tag-java-recursion-example","tag-python-recursion","tag-python-recursive-function","tag-recursion-in-python","tag-recursive-function-in-java"],"yoast_head":"\nPython Recursion - A programmer's most important weapon - TechVidvan<\/title>\n<meta name=\"description\" content=\"Python Recursion - With this article learn the concept of Recursion in Python and also explore its functions, cases and know how to implement them in Python\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/python-recursion\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Python Recursion - A programmer's most important weapon - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Python Recursion - With this article learn the concept of Recursion in Python and also explore its functions, cases and know how to implement them in Python\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/python-recursion\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2020-04-01T08:26:33+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2020\/04\/python-recursive-function.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"802\" \/>\n\t<meta property=\"og:image:height\" content=\"420\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\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":"Python Recursion - A programmer's most important weapon - TechVidvan","description":"Python Recursion - With this article learn the concept of Recursion in Python and also explore its functions, cases and know how to implement them in Python","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:\/\/techvidvan.com\/tutorials\/python-recursion\/","og_locale":"en_US","og_type":"article","og_title":"Python Recursion - A programmer's most important weapon - TechVidvan","og_description":"Python Recursion - With this article learn the concept of Recursion in Python and also explore its functions, cases and know how to implement them in Python","og_url":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2020-04-01T08:26:33+00:00","og_image":[{"width":802,"height":420,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2020\/04\/python-recursive-function.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Python Recursion – A programmer’s most important weapon","datePublished":"2020-04-01T08:26:33+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/"},"wordCount":704,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2020\/04\/python-recursive-function.jpg","keywords":["cases in python recursive function","how python recursive work","java recursion example","python recursion","python recursive function","recursion in python","recursive function in java"],"articleSection":["Python Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/python-recursion\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/","url":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/","name":"Python Recursion - A programmer's most important weapon - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2020\/04\/python-recursive-function.jpg","datePublished":"2020-04-01T08:26:33+00:00","description":"Python Recursion - With this article learn the concept of Recursion in Python and also explore its functions, cases and know how to implement them in Python","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/python-recursion\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2020\/04\/python-recursive-function.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2020\/04\/python-recursive-function.jpg","width":802,"height":420,"caption":"python recursion"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/python-recursion\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Python Recursion – A programmer’s most important weapon"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/77820","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=77820"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/77820\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/77871"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=77820"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=77820"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=77820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}