{"id":265696,"date":"2021-06-03T15:00:54","date_gmt":"2021-06-03T12:00:54","guid":{"rendered":"https:\/\/en.buradabiliyorum.com\/what-is-recursion-in-programming-and-how-do-you-use-it-cloudsavvy-it\/"},"modified":"2021-06-03T15:00:54","modified_gmt":"2021-06-03T12:00:54","slug":"what-is-recursion-in-programming-and-how-do-you-use-it-cloudsavvy-it","status":"publish","type":"post","link":"https:\/\/buradabiliyorum.com\/en\/what-is-recursion-in-programming-and-how-do-you-use-it-cloudsavvy-it\/","title":{"rendered":"#What Is Recursion in Programming, and How Do You Use It? \u2013 CloudSavvy IT"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_84 counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-6a2ebe1120619\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #dd3333;color:#dd3333\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #dd3333;color:#dd3333\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-6a2ebe1120619\" checked aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/buradabiliyorum.com\/en\/what-is-recursion-in-programming-and-how-do-you-use-it-cloudsavvy-it\/#What_Is_Recursion\" >What Is Recursion?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/buradabiliyorum.com\/en\/what-is-recursion-in-programming-and-how-do-you-use-it-cloudsavvy-it\/#The_Dangers_Of_Recursion\" >The Dangers Of Recursion<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/buradabiliyorum.com\/en\/what-is-recursion-in-programming-and-how-do-you-use-it-cloudsavvy-it\/#Use_Recursion_Sparingly\" >Use Recursion Sparingly<\/a><\/li><\/ul><\/nav><\/div>\n<p><strong>&#8220;#What Is Recursion in Programming, and How Do You Use It? \u2013 CloudSavvy IT&#8221;<\/strong><\/p>\n<div id=\"article-content-area\">\n<figure style=\"width: 700px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"type:primaryImage wp-image-11740 size-full\" data-pagespeed-lazy-src=\"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/06\/6c15dccf.png?width=1198&amp;trim=1,1&amp;bg-color=000&amp;pad=1,1\" alt=\"\" width=\"700\" height=\"350\" src=\"https:\/\/www.shutterstock.com\/image-photo\/droste-effect-concept-laptop-apple-eyeglasses-1845526429\" data-credittext=\"Shutterstock\/Olga Donchuk\" onload=\"pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\" onerror=\"this.onerror=null;pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\"\/><figcaption class=\"wp-caption-text\"><span class=\"type:primaryImage imagecredit\"><a rel=\"nofollow noopener\" target=\"_blank\" href=\"https:\/\/www.shutterstock.com\/image-photo\/droste-effect-concept-laptop-apple-eyeglasses-1845526429\">Shutterstock\/Olga Donchuk<\/a><\/span><\/figcaption><\/figure>\n<p>Recursion is an important part of functional programming that can help solve complex problems with elegant solutions. However, it\u2019s important to understand the pros and cons so that it can be done correctly.<\/p>\n<h2 role=\"heading\" aria-level=\"2\"><span class=\"ez-toc-section\" id=\"What_Is_Recursion\"><\/span>What Is Recursion?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The short answer is that Recursion is basically whenever a function calls itself, usually with a different input passed to the child function. It calls itself over and over until an exit condition is reached, and then passes the results back up the call stack, potentially modifying them on the way up as well.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-11726\" data-pagespeed-lazy-src=\"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/05\/beea11a8.png?trim=1,1&amp;bg-color=000&amp;pad=1,1\" alt=\"\" width=\"700\" height=\"382\" src=\"\/pagespeed_static\/1.JiBnMqyl6S.gif\" onload=\"pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\" onerror=\"this.onerror=null;pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\"\/><\/p>\n<p>The long answer is that recursion can help solve complicated problems by breaking them down into smaller subsets of the main problem. Often, you will have data structures containing nested data. Breaking this down into smaller amounts of data will make this easier to process.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-11727\" data-pagespeed-lazy-src=\"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/05\/07de6914.png?trim=1,1&amp;bg-color=000&amp;pad=1,1\" alt=\"\" width=\"700\" height=\"300\" src=\"\/pagespeed_static\/1.JiBnMqyl6S.gif\" onload=\"pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\" onerror=\"this.onerror=null;pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\"\/><\/p>\n<p>For example, say each leaf in the tree had a value associated with it, and we wanted to find the sum of all the values. We could do that with a function like the following, which traverses the tree leaf by leaf, inspecting all the children and calculating the total.<\/p>\n<div class=\"wp-geshi-highlight-wrap5\">\n<div class=\"wp-geshi-highlight-wrap4\">\n<div class=\"wp-geshi-highlight-wrap3\">\n<div class=\"wp-geshi-highlight-wrap2\">\n<div class=\"wp-geshi-highlight-wrap\">\n<div class=\"wp-geshi-highlight\">\n<div class=\"csharp\">\n<pre class=\"de1\"><span class=\"kw4\">int<\/span> CountAllLeaves<span class=\"br0\">(<\/span>Leaf currentLeaf<span class=\"br0\">)<\/span>\n<span class=\"br0\">{<\/span>\n   <span class=\"co1\">\/\/ Start with the current value<\/span>\n   <span class=\"kw4\">int<\/span> Total <span class=\"sy0\">=<\/span> currentLeaf<span class=\"sy0\">.<\/span><span class=\"kw1\">value<\/span><span class=\"sy0\">;<\/span>\n   <span class=\"co1\">\/\/ Add any children to the value, if any<\/span>\n   <span class=\"kw1\">foreach<\/span><span class=\"br0\">(<\/span>Leaf childLeaf <span class=\"kw1\">in<\/span> currentLeaf<span class=\"sy0\">.<\/span><span class=\"me1\">children<\/span><span class=\"br0\">)<\/span> \n   <span class=\"br0\">{<\/span>\n       Total <span class=\"sy0\">=<\/span> Total <span class=\"sy0\">+<\/span> CountAllLeaves<span class=\"br0\">(<\/span>childLeaf<span class=\"br0\">)<\/span><span class=\"sy0\">;<\/span>\n   <span class=\"br0\">}<\/span>\n   <span class=\"kw1\">return<\/span> Total<span class=\"sy0\">;<\/span>\n<span class=\"br0\">}<\/span><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p>This works because\u00a0CountAllLeaves doesn\u2019t care about which Leaf you call it with. It repeatedly calls itself until it hits the final leaf in the tree, which doesn\u2019t have any children. Because of that, it simply returns its own value. That value is passed to the parent leaf, which adds the child\u2019s value to its own, and then repeats for all the siblings that child leaf has.\u00a0In the end, the final result of the function will be the total sum of all the leaves in the tree.<\/p>\n<p>At some point, you must reach the\u00a0<em>halting case<\/em>, which is the piece of the problem that you know the answer to without making any more recursive calls. Otherwise, the function would loop forever, causing the program to crash. In this case, the halting case is when the function reaches a leaf that doesn\u2019t have any children.<\/p>\n<p>It doesn\u2019t have to be about nested data structures like trees. You can write recursive functions around any type of problem. For example, calculating the factorial of a number involves multiplying it by each number smaller than it. You can do this very easily with recursion:<\/p>\n<div class=\"wp-geshi-highlight-wrap5\">\n<div class=\"wp-geshi-highlight-wrap4\">\n<div class=\"wp-geshi-highlight-wrap3\">\n<div class=\"wp-geshi-highlight-wrap2\">\n<div class=\"wp-geshi-highlight-wrap\">\n<div class=\"wp-geshi-highlight\">\n<div class=\"csharp\">\n<pre class=\"de1\"><span class=\"kw4\">int<\/span> Factorial<span class=\"br0\">(<\/span><span class=\"kw4\">int<\/span> n<span class=\"br0\">)<\/span>\n<span class=\"br0\">{<\/span>\n   <span class=\"kw1\">if<\/span> <span class=\"br0\">(<\/span>n <span class=\"sy0\">&lt;=<\/span> <span class=\"nu0\">1<\/span><span class=\"br0\">)<\/span>\n       <span class=\"kw1\">return<\/span> <span class=\"nu0\">1<\/span><span class=\"sy0\">;<\/span>\n\u00a0\n   <span class=\"kw1\">return<\/span> n <span class=\"sy0\">*<\/span> Factorial<span class=\"br0\">(<\/span>n<span class=\"sy0\">-<\/span><span class=\"nu0\">1<\/span><span class=\"br0\">)<\/span><span class=\"sy0\">;<\/span>\n<span class=\"br0\">}<\/span><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p>In this example, the halting case is when <code>n<\/code>\u00a0reaches 1, where it finally returns a value and the call stack can be collapsed.<\/p>\n<p>Lets look at a real-world example. In this bit of code, there is a <code>Container<\/code>\u00a0class which contains multiple UI elements attached to it, as well as multiple child containers with their own elements. It must be \u201crendered\u201d out to a flat list of elements which can be shown on screen.<\/p>\n<p>This is basically another tree data structure, so the <a href=\"https:\/\/buradabiliyorum.com\/en\/category\/download-scripts-themes-apps\/\" data-internallinksmanager029f6b8e52c=\"9\" title=\"Download Scripts &amp; Themes &amp; Apps\" target=\"_blank\" rel=\"noopener\">app<\/a>roach is similar. Except, in this case, the total variable is a list, which gets the Elements lists of each Container appended to it.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-11733\" data-pagespeed-lazy-src=\"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/05\/aa45d96d.png?trim=1,1&amp;bg-color=000&amp;pad=1,1\" alt=\"\" width=\"696\" height=\"383\" src=\"\/pagespeed_static\/1.JiBnMqyl6S.gif\" onload=\"pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\" onerror=\"this.onerror=null;pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\"\/><\/p>\n<p>The magic of doing it using recursion is that it preserves the Z-order of the elements. Elements drawn after other elements go on top, so the youngest child container will always display on top. In this scenario, I also found it useful to display overlay elements, which get added after the other elements and children finish rendering.<\/p>\n<h2 role=\"heading\" aria-level=\"2\"><span class=\"ez-toc-section\" id=\"The_Dangers_Of_Recursion\"><\/span>The Dangers Of Recursion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>So, when should you use recursion in your code? The answer is you should actually probably avoid it in most situations, especially when an iterative solution using a simple loop will get the job done.<\/p>\n<p>Every time you call a function, your program allocates resources towards that function. All local variables and info go onto the stack, which is a Last-In, First-Out (LIFO) data structure. This means the latest function call is always the first to be removed, like a bucket where you always remove the top element.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-11736\" data-pagespeed-lazy-src=\"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/06\/00b7a78e.png?trim=1,1&amp;bg-color=000&amp;pad=1,1\" alt=\"\" width=\"700\" height=\"311\" src=\"\/pagespeed_static\/1.JiBnMqyl6S.gif\" onload=\"pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\" onerror=\"this.onerror=null;pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\"\/><\/p>\n<p>The problem with recursion is that it can use a nested function call for each element being processed. This results in a lot more overhead, as each function call needs its own set of local variables and parameters. It will take extra processing time compared to a loop based approach.<\/p>\n<p>Loops don\u2019t have this problem. After each loop iteration, the stack will have the top element cleared off. It could process a billion elements using the same stack.<\/p>\n<p>If you use too many resources with recursive function calls, it can result in <em>stack overflow,\u00a0<\/em>where the program can crash just based on too many nested calls. This can happen with particularly large data sets, or with poor algorithms like binary or exponential recursion, which call themselves multiple times per function call.<\/p>\n<h2 role=\"heading\" aria-level=\"2\"><span class=\"ez-toc-section\" id=\"Use_Recursion_Sparingly\"><\/span>Use Recursion Sparingly<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Recursion is a nice thing to have for certain problems, but there are basically no recursive solutions to problems that can\u2019t also be solved using loops (except for nested recursion like <a rel=\"nofollow noopener\" target=\"_blank\" href=\"https:\/\/en.wikipedia.org\/wiki\/Ackermann_function\">Ackerman\u2019s function<\/a>). Even complicated tree data structures <a rel=\"nofollow noopener\" target=\"_blank\" href=\"https:\/\/www.geeksforgeeks.org\/inorder-tree-traversal-without-recursion\/\">can be traversed using loops and stacks<\/a>. If you need to handle large amounts of data, or care a lot about performance, you might be better off using an iterative solution.<\/p>\n<p>The other problem with recursion is that it can lead to code that is difficult for other people to understand, as it usually takes a bit of head scratching before someone gets it. While it often seems like the more \u201celegant\u201d solution, your job as a programmer is not to show off, and is instead to write functional, readable code.<\/p>\n<p>In any case, you\u2019ll want to think about whether or not the problem at hand would be better off using a loop. Recursion should be your last resort for problems that would be much more complicated without it. In fact, in my entire 40,000 lines of source code, I only had one example of recursion for this article.<\/p>\n<p>And, after a second glance at it, I actually noticed a problem. While it worked fine, it was written the lazy, obvious way, and as such is using a lot more memory than it needs. This isn\u2019t really a problem with the small data structures it\u2019s handling, but it was creating a <code>new List&lt;CuiElement&gt;()<\/code>\u00a0for each call of the function, and adding the results of the children below it. This meant that if it was given a container with deeply nested children, it would be storing the same data over and over for no reason.<\/p>\n<p>The solution in this case was to pass the recursive function a reference to an external list, and add all the elements to it directly. This also involved changing the <code>Render()<\/code>\u00a0function into a function that handled the top-level setup for the recursive build function.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-11739\" data-pagespeed-lazy-src=\"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/06\/20473719.png?trim=1,1&amp;bg-color=000&amp;pad=1,1\" alt=\"\" width=\"700\" height=\"448\" src=\"\/pagespeed_static\/1.JiBnMqyl6S.gif\" onload=\"pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\" onerror=\"this.onerror=null;pagespeed.lazyLoadImages.loadIfVisibleAndMaybeBeacon(this);\"\/><\/p>\n<p>This accomplishes exactly the same solution of adding each element in the proper order, but fixes the problem of memory usage going up exponentially with each call.<\/p>\n<p>Still, I\u2019m happy with this function as it\u2019s quite concise and gets the job done easily. If I was to convert this to a solution using a loop, it would be a lot more complicated and do the exact same thing. You will need to weigh the pros and cons of using a recursive solution, and only use them where you\u2019re not expecting serious resource usage. In this case, I\u2019m not expecting to be calling this function with nested containers that are hundreds of elements deep, so using recursion here is fine.<\/p>\n<hr\/>\n<p>For more info on this topic, see our guide to Recursion.\n<\/p><\/div>\n<blockquote><p><strong><span style=\"color: #ff6600;\">If you liked the article, do not forget to share it with your friends. Follow us on\u00a0<span style=\"color: #ff0000;\"><a style=\"color: #ff0000;\" href=\"https:\/\/news.google.com\/publications\/CAAqBwgKMLG0nwswvr63Aw\" target=\"_blank\" rel=\"nofollow noopener noreferrer\">Google News<\/a><\/span>\u00a0too, click on the star and choose us from your favorites.<\/span><\/strong><\/p><\/blockquote>\n<blockquote>\n<p style=\"text-align: center;\">For forums sites go to <span style=\"color: #ff9900;\"><a style=\"color: #ff9900;\" href=\"https:\/\/forum.buradabiliyorum.com\/\" target=\"_blank\" rel=\"noopener\">Forum.BuradaBiliyorum.Com<\/a><\/span><\/strong><\/p>\n<\/blockquote>\n<blockquote>\n<p style=\"text-align: center;\"><strong>If you want to read more like this article, you can visit our <span style=\"color: #ff9900;\"><a style=\"color: #ff9900;\" href=\"https:\/\/en.buradabiliyorum.com\/technology\/\" target=\"_blank\" rel=\"noopener\">Technology category.<\/a><\/span><\/strong><\/p>\n<\/blockquote>\n<p><span style=\"color: black;\"><a style=\"color: #ff9900;\" href=\"https:\/\/www.cloudsavvyit.com\/11720\/what-is-recursion-in-programming-and-how-do-you-use-it\/\" target=\"_blank\" rel=\"noopener\">Source<\/a><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>&#8220;#What Is Recursion in Programming, and How Do You Use It? \u2013 CloudSavvy IT&#8221; Shutterstock\/Olga Donchuk Recursion is an important part of functional programming that can help solve complex problems with elegant solutions. However, it\u2019s important to understand the pros and cons so that it can be done correctly. What Is Recursion? The short answer&#8230;<\/p>\n","protected":false},"author":1,"featured_media":265697,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"https:\/\/www.cloudsavvyit.com\/p\/uploads\/2021\/06\/6c15dccf.png","fifu_image_alt":"","footnotes":""},"categories":[18],"tags":[],"class_list":["post-265696","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-technology"],"_links":{"self":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/posts\/265696","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/comments?post=265696"}],"version-history":[{"count":0,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/posts\/265696\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/media\/265697"}],"wp:attachment":[{"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/media?parent=265696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/categories?post=265696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/buradabiliyorum.com\/en\/wp-json\/wp\/v2\/tags?post=265696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}