{"id":1907,"date":"2014-11-14T00:00:00","date_gmt":"2014-11-14T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/rethinking-the-practicalities-of-recursion\/"},"modified":"2021-05-17T18:35:58","modified_gmt":"2021-05-17T18:35:58","slug":"rethinking-the-practicalities-of-recursion","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/development\/dotnet-development\/rethinking-the-practicalities-of-recursion\/","title":{"rendered":"Rethinking the Practicalities of Recursion"},"content":{"rendered":"
\n

It is rare for a technical interview to end without a recursion question being asked of the candidate. Despite this, recursion rarely shows up in production code. It seems that experienced object oriented developers tend to favor loops in their production code.  Why?<\/p>\n

This article explores this conundrum, as well as recursion and its use in C#.<\/p>\n

Recursion<\/h1>\n

Before you can understand recursion as a programming technique, you need to understand it; and appreciate the main alternative – iteration. Iteration has to be understood over and over again.<\/p>\n

Definition<\/h2>\n

Computer science provides a modest explanation of recursion, the decomposition of a problem’s solution into subsets of the same solution. In other words, the coding of a method which calls itself with smaller inputs to find an answer. Whatever way we define recursion though, we need to mention  the two elements underlying recursive solutions. Firstly, methods call themselves. Secondly, and most importantly, each subsequent call will involve smaller chucks of the initial problem until it can be solved without further recursion.  <\/p>\n

Two canonical examples of recursion are frequently found in the programming textbooks. The first and simpler one is that of calculating a factorial.  Here, as an example, is a C# version. Recursion<\/code> contains the two requisite elements of calling itself with ever decreasing input values. The bounds check, if (input < 2)<\/code> , ensures exit as the input parameter decreases.  <\/p>\n

\n        public static int Recursion(int input)\n        {\n            if (input < 2) return 1; \n            \n            return input * Recursion(input - 1);\n        }\n<\/pre>\n
Variants of our  next example, the node-finder, permeates computer science algorithm studies and differs meaningfully from calculating  numerical values. The code searches for a specific node contained within a simple tree data structure.<\/p>\n
    public class BinaryNode\n    {\n        public int Value { get; set; }\n        public BinaryNode Smaller { get; set; }\n        public BinaryNode Larger { get; set; }\n\n        public static BinaryNode Find(BinaryNode node, int value)\n        {\n            if (node == null) return null;\n            if (node.Value == value) return node;\n\n            if (node.Smaller != null && node.Smaller.Value >= value)\n                return Find(node.Smaller, value);\n\n            return Find(node.Larger, value);\n        }\n    } \n\t<\/pre>\n
 Unlike our previous factorial example,  there is no explicit coding of that element of recursion that involves the winnowing-down of the problem set with each  recursive call.  Find assumes that the underlying tree structure is built as visualized below, with every node having one parent and a parent  that only optionally references two child nodes. Also, traversing the tree from the bottom always ends at the root;  going down always reaches a null; and there’s only one path between nodes.  <\/p>\n<\/p>\n
Recursion Versus Iteration<\/h2>\n
According to  computer science theory, any recursive method can be re-written iteratively. We can easily demonstrate this when we are  computing factorials. The similarity between the   Loop<\/code> method and its recursive  brethren is striking. It, too, repeatedly calls a similar piece of code,   result *= <\/code>i<\/code> , while whittling  down the problem via a for-each loop.<\/p>\n
        public static int Loop(int input)\n        {\n            if (input < 2) return 1;\n\n            var result = 1;\n\n            for (var i = 2; i <= input; i++)\n                result *= i;\n\n            return result;\n        }\n<\/pre>\n
The larger volume  of code of the iterative solution becomes obvious when you compare the different forms of computation.   Loop<\/code> contains more code to  prepare and execute it’s for-each, as well as the seemingly superfluous   return<\/code> statement. In addition to  requiring fewer keystrokes, some might even argue that if code can smell then the recursive factorial method has a  beautiful fragrance.<\/p>\n
Computer science  does not tell us when to employ either recursion or iteration. By revisiting our   BinaryNode<\/code> ‘s   FindLoop<\/code> method, we soon get a  hint why it does not. The recursive factorial is shorter and sweeter than its iterative twin, and likewise the iterative  tree-Node finder,   FindLoop<\/code> looks more awkward than  its recursive peer. <\/p>\n
        public static BinaryNode FindLoop(BinaryNode node, int value)\n        {\n            var current = node;\n\n            while (current != null)\n            {\n                if (current.Value == value) return current;\n\n                if (current.Smaller != null && current.Smaller.Value >= value)\n                    current = current.Smaller;\n                else\n                    current = current.Larger;\n            }\n\n            return current;\n        }\n    \n<\/pre>\n
 Whatever importance you attach to the  looks of the code, both versions of   Find get the same results without  significant differences. Recursion does not seem, at first glance, to offer any intrinsic benefits over iteration beyond  the elegance of the code. Most developers who face the choice between recursion and iteration will usually fall back on  personal preference. <\/p>\n
Preferences<\/h1>\n
It is tricky to try  to explain preferences. As this article’s opening comments suggest, people can apparently hold opposing positions at the  same time. Developers often show that they favor recursion by the relish with which they ask recursion-based interview  questions, yet they rarely employ recursion in their applications. A recent academic study by Gunnar R. Bergersen and  Dag I.K. Sjøberg,   Evaluating Methods and Technologies in Software  Engineering with Respect to Developers’ Skill Level<\/a>,  indirectly suggest explanations for this apparent paradox.<\/p>\n
Bergersen and  Sjøberg begin their paper recounting an earlier study highlighting developer-preferences for recursion over iteration.  Only one problem though: the developers questioned for the study were all computer science students in school, and we  all know that nobody leaves an algorithms course without an uncritical  love of  recursion. Their more recent study targeted, in contrast, experienced developers. There the results differed  dramatically.<\/p>\n
They discovered  that inexperienced programmers tended to write noticeably buggier, albeit better performing, code when employing  iterative techniques compared to recursion. Experienced programmers on the other hand wrote significantly less error  prone and faster routines with iteration. It looked as if skilled professionals lost their youthful passion for  recursion when faced with quality and delivery deadlines. And therein lies an explanation for the observed paradox.  Developers learn and admire recursion’s theoretical promise, so they ask job applicants about it, but they learn over  time that it’s a tough promise to deliver upon when compared to iteration. Maybe they also ask the question to make sure  the applicants were awake during their college course.<\/p>\n
Pitfalls<\/h1>\n
Recursion’s fall  from the esteem that it gets from academics begs the obvious question: What are the pitfalls? What follows are some of  the more likely ones.<\/p>\n
Size<\/h2>\n
Repeated arithmetic  calculations can generate big values. While recursion isn’t unique in suffering from the consequences of this, it is  prone to overflow exceptions and incorrect output due to not setting explicit bounds. Calculating the factorial for 30  with our sample recursive factorial routine highlights this risk. The correct answer equals  265,252,859,812,191,058,636,308,480,000,000; which far exceeds the modest limits of our   Recursion<\/code> method’s parameter,  variables, and the output value’s size limit.<\/p>\n
We can solve this  by adding the following methods to our   Factorial<\/code> class. The first allows  us to catch the   OverflowException<\/a> via a  checked<\/a> block. Adding it forces the typically configured .NET complier to not<\/u> ignore such exceptions.<\/p>\n
        public static int RecursionChecked(int input)\n        {\n            checked { return input < 2 ? 1 : input * Recursion(input - 1); }\n        }\n<\/pre>\n
The next method  gives our class the capability of handling data types larger than an   int<\/code> for a correct factorial  value. It leverages the   BigInteger<\/a> struct, contained within the System.Numerics namespace which was first provided by .NET 4.0<\/p>\n
        public static BigInteger RecursionBig(BigInteger input)\n        {\n            return input < 2 ? 1 : input * RecursionBig(input - 1);\n        }\n<\/pre>\n
When running all  three flavors of our recursive method, the size issue jumps out. Note the unchecked version,   Recursion<\/code> , happily eats the   OverflowException<\/code> ; truncates any  intermediary values; and returns the incorrect 1,409,286,144. <\/p>\n
 \"2096-img5E.gif\"<\/p>\n
Bad Data<\/h2>\n
Our   BinaryNode<\/code> sample provides its  own cautionary tales when working with complex object-based structures. While iterative code can suffer the same fate as  recursion when computing values, recursion can make you particularly vulnerable to hazardous assumptions about the  underlying data. While we only examine two common issues associated with trees, many others exist.<\/p>\n
The first potential  problem happens regularly in the field and involves trees containing a node referencing a second parent. While looping  structures lend themselves to a simple explicit exit condition to avoid such potential runaway searches, recursive  methods by their nature do not. Our   Find<\/code> method will go merrily  searching for node 42 until a   StackOverflow<\/code> exception pops.<\/p>\n
 \"2096-img63.jpg\"<\/p>\n
A subtler problem  involves tree structures not conforming to expectations. The   unbalanced tree<\/a> stands  out as a classic example of this phenomena. An unwary developer could easily assume that all node trees to be balanced  with a limited number of levels. What if the tree is unbalanced as pictured below? Searches will not break, they just  may take considerably longer than expected. \t<\/p>\n
 \t\"2096-img64.jpg\"<\/p>\n
\n
When Recursion Rocks<\/h4>\n
Navigating  \t\tquestionable data structures hints at one of recursion’s more successful use cases. When the same recursive code  \t\tcreates the underlying structure, then reading it is not nearly as risky. This “create and read” pattern gives  \t\tplay to many well-known algorithms, such as,  \t\tQuickSort<\/i><\/a> and <\/i> \t\tMergeSort<\/i><\/a>, where recursive ‘<\/i>divide  \t\tand conquer<\/i><\/a>‘  \t\talgorithms shine.<\/i><\/p>\n<\/p><\/div>\n
Performance<\/h2>\n
Recursion does not  guarantee acceptable performance. In fact, the very usage of recursive algorithms in managed code exacts a small  performance penalty. Whether this penalty is worth it is a discussion best left to the same folks concerned with the  costs and benefits of garbage collection.  Unsuspecting developers though can  easily create their very own significant performance issues.<\/p>\n
Consider the  following implementation of a  Fibonacci<\/a> number. It applies recursion in a somewhat straightforward, simplistic fashion.<\/p>\n
    public static class Fibonacci\n    {\n        public static int Recursion(int input)\n        {\n            if (input < 1) return 0;\n            if (input < 2) return 1;\n            \n            return Recursion(input - 1) + Recursion(input - 2);\n        }\n<\/pre>\n
Adding crude  execution time checks to the above provides some scary results. Graphing   input<\/code> values ranging from 20 to  45 against the   Recursion<\/code> method’s execution  times suggests performance problems exist with our implementation as shown in the exponentially increasing execution  time versus linearly growing   input<\/code> values.<\/p>\n
 \"2096-img66.jpg\"<\/p>\n
Given that   Recursion<\/code> calls itself twice the  exponential slope on the logarithmic graph seems reasonable. Avoiding fast breeding recursive calls when calculating a  Fibonacci numbers via recursion requires a little less theory and more practical concerns as demonstrated in   Recursion<\/code>Pragmatic<\/code> .<\/p>\n
        \n        public static int RecursionPragmatic(int input)\n        {\n            if (input < 1) return 0;\n            if (input < 2) return 1;\n            \n            return RecursionTail(input, 0, 1);\n        }\n\n        private static int RecursionTail(int input, int first, int second)\n        {\n            if (input < 3) return first + second;\n\n            return RecursionTail(input - 1, second, first + second);\n        }\n\n<\/pre>\n
A few timing  comparisons with   Recursion<\/code>  and   RecursionPragmatic <\/code> confirm the  payoff of incorporating some practical touches into a recursive method.  <\/code><\/p>\n
\"2096-img69.gif\"<\/p>\n
\n
Tail Call<\/h4>\n
Experienced  \t\tfunctional programmers long ago developed techniques for managing state via parameters. The technique, generally  \t\tknown as a  \t\ttail call<\/i><\/a>, solves other troubling problems too but its effectiveness depends on the runtime and complier. For  \t\texample, F# fully exploits .NET’s tail call optimizations whereas C# demands a little coaxing as noted in  \t\t<\/i> \t\t \t\tMSDN<\/i><\/a>.<\/i><\/p>\n<\/p><\/div>\n
  Recursion<\/code>Pragmatic<\/code> owes its  success to the fact that   RecursionTail<\/code> drags around all required state for computation via its parameters. This  practical approach limits the   Recursion<\/code>Pragmatic’s  stack footprint to a minimal  collection of pointers.<\/p>\n
Before leaving this  discussion, savvy readers will have noticed that the code samples are only sketches. They aren’t satisfactory.  Calculating Fibonacci numbers under more severe real-world scenarios demands complex techniques, some of which leverage  recursion in an equally complex fashion. <\/p>\n
Debugging<\/h2>\n
Unraveling a deep  call stack to find that errant instance of a recursive method can be painful. Experience suggests injecting logging  similar to that demonstrated in   RecursionBlowup<\/code> as the only  foolproof defense.<\/p>\n
        public static int RecursionBlowup(int input)\n        {\n            if (input == 7)\n                throw new Exception(string.Format(\"Hit by a {0}!\", input));\n            \n            return input < 2 ? 1 : input * RecursionBlowup(input - 1);\n        }\n<\/pre>\n
Only one trouble  with logging. Developers must know beforehand what to watch out for in order to properly log it. Imagine we did not know  the dangers of being seven? The sample debugging screen shot below promises a long walk down stack trace lane..<\/p>\n
 \t\"2096-img4A.jpg\"<\/p>\n
Avoiding Pitfalls<\/h2>\n
Given the above  pitfalls, here are a few suggestions for avoiding them when working with recursion.<\/p>\n
    \n
  1.  Manipulating large values or complex objects will likely require explicit type, and boundary, checks  \t\tsuch as those found within an iterative implementations.<\/li>\n
  2.  Applying simplistic recursive thinking without care  may lead to incorrect results and  \t\tperformance issues.<\/li>\n
  3.  Maintaining state within a deep recursive call chain may demand refactoring or workarounds, such as,  \t\ttail calls.  <\/li>\n
  4.  Debugging difficulties that are encountered when using  non-trivial recursive methods may dictate  \t\tlogging and perseverance.<\/li>\n<\/ol>\n
    Conclusion<\/h1>\n
    Our recursion  excursion covered a good deal of practical ground. We reviewed recursion and explored why experienced developers talk  ‘recursion’ but code ‘iteration’. And while definitive guidelines for writing recursive methods must remain implementation-specific,  some well-known pitfalls that I’ve described should suggest to you about when to use recursion.<\/p>\n
    Finally and  hopefully, the article’s abstemiousness with recursion jokes compensated the reader for whatever its code lacked in  correctness or beauty. <\/p>\n
    \n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"
    We all love recursion right up to the point of actually using it in production code. Why?  Recursion can illustrate in code many of the excellent ‘divide and conquer’ algorithms, but will always provide the compiler with a challenge to implement as efficiently as an iterative solution, and can present the programmer a puzzle to test, debug and render resilient to bad data. …<\/p>\n","protected":false},"author":200451,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143538],"tags":[4143,4229],"coauthors":[],"class_list":["post-1907","post","type-post","status-publish","format-standard","hentry","category-dotnet-development","tag-net","tag-net-framework"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1907","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/200451"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=1907"}],"version-history":[{"count":5,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1907\/revisions"}],"predecessor-version":[{"id":91086,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1907\/revisions\/91086"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=1907"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=1907"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=1907"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=1907"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}