{"id":438,"date":"2019-07-18T14:59:40","date_gmt":"2019-07-18T14:59:40","guid":{"rendered":"http:\/\/askpython.com\/?p=438"},"modified":"2019-09-05T05:58:06","modified_gmt":"2019-09-05T05:58:06","slug":"python-recursion-function","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/python-recursion-function","title":{"rendered":"Python Recursion Example &#8211; Recursive Functions"},"content":{"rendered":"\n<p>When a <a href=\"https:\/\/www.askpython.com\/python\/python-functions\" target=\"_blank\" rel=\"noreferrer noopener\" label=\"function (opens in a new tab)\">function<\/a> calls itself, it&#8217;s called a recursive function. In this tutorial, we will learn how to write Python recursion function.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">What is Recursion in Python?<\/h2>\n\n\n\n<p>When a function is defined in such a way that it calls itself, it&#8217;s called a recursive function. This phenomenon is called recursion. Python supports recursive functions.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Do we really need Recursive Functions?<\/h2>\n\n\n\n<p>The recursion is very similar to a loop where the function is called in every iteration. That&#8217;s why we can always use loops as a replacement for Python recursion function.<\/p>\n\n\n\n<p>But, some programmers prefer recursion over loops. It&#8217;s a matter of choice mostly and you are free to either use loops or recursion. <\/p>\n\n\n\n<figure class=\"wp-block-embed-wordpress wp-block-embed is-type-wp-embed is-provider-python-tutorials\"><div class=\"wp-block-embed__wrapper\">\n<blockquote class=\"wp-embedded-content\" data-secret=\"m4DomawPlj\"><a href=\"https:\/\/www.askpython.com\/python\/python-for-loop\">Python for Loop<\/a><\/blockquote><iframe loading=\"lazy\" class=\"wp-embedded-content\" sandbox=\"allow-scripts\" security=\"restricted\" style=\"position: absolute; visibility: hidden;\" title=\"&#8220;Python for Loop&#8221; &#8212; AskPython\" src=\"https:\/\/www.askpython.com\/python\/python-for-loop\/embed#?secret=zVhdfsBcwP#?secret=m4DomawPlj\" data-secret=\"m4DomawPlj\" width=\"600\" height=\"338\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\"><\/iframe>\n<\/div><\/figure>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Python Recursion Function Examples<\/h2>\n\n\n\n<p>Let&#8217;s look into a couple of examples of recursion function in Python.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">1. Factorial of an Integer<\/h3>\n\n\n\n<p>The factorial of an integer is calculated by multiplying the integers from 1 to that number. For example, the factorial of 10 will be 1*2*3&#8230;.*10.<\/p>\n\n\n\n<p>Let&#8217;s see how we can write a factorial function using the for loop.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef factorial(n):\n    result = 1\n\n    for i in range(1, n + 1):\n        result = result * i\n\n    return result\n\n\nprint(f&#039;Factorial of 10 = {factorial(10)}&#039;)\nprint(f&#039;Factorial of 5 = {factorial(5)}&#039;)\n<\/pre><\/div>\n\n\n<p>Let&#8217;s see how can we change the factorial() function to use recursion.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef factorial(n):\n    if n == 1:\n        return 1\n    else:\n        return n * factorial(n - 1)\n\n\nprint(f&#039;Factorial of 10 = {factorial(10)}&#039;)\nprint(f&#039;Factorial of 5 = {factorial(5)}&#039;)\n<\/pre><\/div>\n\n\n<p>The below image shows the execution of the recursive function.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"528\" height=\"334\" src=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-recursion-function-example.png\" alt=\"Python Recursion Function Example\" class=\"wp-image-440\" srcset=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-recursion-function-example.png 528w, https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-recursion-function-example-300x190.png 300w\" sizes=\"auto, (max-width: 528px) 100vw, 528px\" \/><figcaption>Python Recursion Function Example<\/figcaption><\/figure><\/div>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">2. Fibonacci Series<\/h3>\n\n\n\n<p>The Fibonacci series is the sequence of numbers where each number is the sum of two preceding numbers. For example &#8211; 1, 1, 2, 3, 5, 8, 13, 21 and so on.<\/p>\n\n\n\n<p>Let&#8217;s look at a function to return Fibonacci series numbers using loops. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef fibonacci(n):\n    &quot;&quot;&quot; Returns Fibonacci Number at nth position using loop&quot;&quot;&quot;\n    if n == 0:\n        return 0\n    if n == 1:\n        return 1\n    i1 = 0\n    i2 = 1\n    num = 1\n    for x in range(1, n):\n        num = i1 + i2\n        i1 = i2\n        i2 = num\n    return num\n\n\nfor i in range(10):\n    print(fibonacci(i), end=&quot; &quot;)\n\n# Output: 0 1 1 2 3 5 8 13 21 34 \n<\/pre><\/div>\n\n\n<p>Here is the implementation of the fibonacci() function using recursion.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef fibonacci(n):\n    &quot;&quot;&quot; Returns Fibonacci Number at nth position using recursion&quot;&quot;&quot;\n    if n == 0:\n        return 0\n    elif n == 1:\n        return 1\n    else:\n        return fibonacci(n - 1) + fibonacci(n - 2)\n\n\nfor i in range(10):\n    print(fibonacci(i), end=&quot; &quot;)\n\n# Output: 0 1 1 2 3 5 8 13 21 34 \n<\/pre><\/div>\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"322\" src=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-fibonacci-series-using-recursion-1024x322.png\" alt=\"Python Fibonacci Series Using Recursion\" class=\"wp-image-442\" srcset=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-fibonacci-series-using-recursion-1024x322.png 1024w, https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-fibonacci-series-using-recursion-300x94.png 300w, https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-fibonacci-series-using-recursion-768x242.png 768w, https:\/\/www.askpython.com\/wp-content\/uploads\/2019\/07\/python-fibonacci-series-using-recursion.png 1118w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption>Python Fibonacci Series Using Recursion<\/figcaption><\/figure><\/div>\n\n\n\n<p>Here recursive function code is smaller and easy to understand. So using recursion, in this case, makes sense.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">What is the Base Case in Recursion?<\/h2>\n\n\n\n<p>While defining a recursive function, there must be at least one base case for which we know the result. Then every <strong>successive recursive function call must bring it closer to the base case<\/strong>. This is required so that eventually the recursive calls terminate. Otherwise, the function will never terminate and we will get out of memory error.<\/p>\n\n\n\n<p>You can check this behavior in both the above examples. The recursive function call arguments are getting closer to the base case.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Advantages of Recursion<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>Sometimes recursion reduces the number of lines of code.<\/li><li>The recursion code looks simple.<\/li><li>If we know the base case, then using recursion in a function is easier.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Disadvantages of Recursion<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>If not implemented properly, the function will never terminate.<\/li><li>Understanding recursion is more confusion when compared to loops.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Recursion or Loops?<\/h2>\n\n\n\n<p>It&#8217;s a matter of personal choice. I always prefer loops over recursion. I haven&#8217;t seen any example where we can&#8217;t use loops and have to use recursion only.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">References:<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Recursion_(computer_science)\" target=\"_blank\" rel=\"noreferrer noopener\" aria-label=\"Wikipedia (opens in a new tab)\">Wikipedia<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>When a function calls itself, it&#8217;s called a recursive function. In this tutorial, we will learn how to write Python recursion function. What is Recursion in Python? When a function is defined in such a way that it calls itself, it&#8217;s called a recursive function. This phenomenon is called recursion. Python supports recursive functions. Do [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-438","post","type-post","status-publish","format-standard","hentry","category-python"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/438","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=438"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/438\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=438"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=438"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=438"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}