Answers.Body: <blockquote>
    <p>"Why are we learning recursion? Is it good programming practice?"</p>
  </blockquote>
  
  <p>Most things in programming should be thought of as <strong>tools</strong>. Languages are tools. Algorithms are tools. Various approaches are tools.</p>
  
  <p>Different tools are for different jobs. A carpenter learns about a hammer, a saw, a wrench, etc because sometimes the hammer will be the best tool for the job, sometimes it'll be the saw, and sometimes it'll be the wrench. Sometimes, the best tool will be something the carpenter has never used before! But the more tools they already know, the easier it'll be to learn about new tools. Having learned about a wrench makes it easier to learn about a screwdriver when you need to. So learning about a tool is never wasted time: even if we don't use the tool every day, it helps us learn about stuff we need to know.</p>
  
  <p>That's why we learn about a bunch of different things in programming. Sometimes a loop will be the best tool. Sometimes a recursive function will be the best tool. Sometimes we'll even come across new ideas and approaches! And we can use the tools we've already learned about to help learn about these new tools.</p>
  
  <p>So even if recursion doesn't solve every problem (just like a hammer doesn't cover everything a carpenter has to do), it's still worth learning about because it adds a tool to our toolbelt.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-20T21:44:24.517Z
Answers.LastActivityDate: 2017-07-20T21:44:24.517Z
Answers.UserDisplayName: Kevin Workman
Answers.Body: <p>A professional programmer could go most of her or his career without having to resort to it. The pros, some problems/algorithms are just not very tractable outside of a recursive approach (I usually assign the flood fill algorithm in my AP or post-AP classes). These tend to be rare. Cons, very prone to error, the algorithms may not be particularly intuitive and in most cases can be replaced with an iterative approach. Besides Flood Fill, the recursive solution to the Tower of Hanoi problem is another powerful illustration of how powerful a recursive algorithm can be.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T16:21:41.960Z
Answers.Text: *This doesn't exactly answer the question.* The question was about getting students to be excited about recursion, as well as other things that are specifically written in the question.
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T16:11:10.087Z
Answers.LastActivityDate: 2017-06-07T16:11:10.087Z
Answers.UserDisplayName: paulMD
Answers.Body: <p>I feel it is very bad to say "no, don't ever use this".</p>
  
  <p>For recursion, the second most important detail is to have an <code>exit statement</code>. That is the condition upon which the recursion terminates. So long as the exit statement is good, recursion is a very, very powerful tool.</p>
  
  <pre><code>def thing(position, str):
      if position == 0:
          print(str)
          return str
      else:
          print("single letters: "+thing(position-1, str[:,position]))
          return thing(position-1, str[:,position])
  </code></pre>
  
  <p>This has a well defined exit statement, that will be met, because every call decreases <code>position</code> by 1, and the exit checks if <code>position</code> is 0. Which eventually happens for any positive integer value being decremented.</p>
  
  <p>This shows that recursion is very useful, BUT it <strong>must</strong> have a good exit statement. So saying "it's horrible in any programming language" is <em>very</em> misleading.</p>
  
  <p>So in essence, the main point is showing how important choosing a good exit statement is. It has to be one that must be met, simply because of the recursive action (in the example, the <code>position-1</code> parameter being passed, and the <code>position==0</code> check).</p>
  
  <p>NOTE: this is code adapted from java, so it might have inaccuracies. Feel free to correct them.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:24:31.787Z
Answers.Text: I agree that "it's horrible in any programming language" is misleading, but they don't know about functional languages and, as a CS1 class, its hard to appreciate side-effect free design. I fear the nuances of when recursion is a good design choice is hard to describe in CS1. (Your observation about an 'exit' statement is essentially 'you need a base case' and is something we cover and not, itself, answer to "when is recursion good practice?"). I'll revise my question to be clearer.
Answers.UserDisplayName: GermaneDork
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:25:50.407Z
Answers.Text: @GermaneDork yes. As I said, you should explain the importance of good exit statements. Ones that must happen, to avoid a stackoverflow,
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:40:14.220Z
Answers.Text: @GermaneDork oh. Well then I'll revise my answer, for future readers
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-19T00:04:55.923Z
Answers.Text: You don't need a base case. `def receive(event): process(event); receive(eventstream.next); end` is a perfectly good way of writing an operating system, for example. Operating systems don't have a base case, they should *never* stop.
Answers.UserDisplayName: Jörg W Mittag
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:19:22.743Z
Answers.LastActivityDate: 2017-06-07T05:19:22.743Z
Answers.UserDisplayName: ItamarG3
Answers.Body: <p>To answer this question I would say it depends on the context. For something such as Quick sort then yes, however if recursion could be replaced by iterating a function call then it is often easier for a programmer to identify a particular point in a program and where it has been executed (useful for debugging).  It all depends on the level of confidence in the programmer, and the actual requirement for recursion to solve the problem.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T09:32:21.907Z
Answers.Text: Could you please clarify or add details to the questions asked?
  
  e.g.: *"My question(s): how do I get students excited about recursion? How do I better motivate studying recursion? Can I better / more naturally express those conditions under which (or those languages for which) recursion is not a poor design choice?"*
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T09:21:40.710Z
Answers.LastActivityDate: 2017-06-07T09:21:40.710Z
Answers.UserDisplayName: Paul Meehan
Answers.Body: <p>Quite honestly, I would be upfront with them about the debate. Send them to a couple other SE threads:</p>
  
  <ul>
  <li><p><a href="https://stackoverflow.com/questions/9386375/efficiency-recursion-vs-loop">Efficiency: recursion vs loop</a></p></li>
  <li><p><a href="https://stackoverflow.com/questions/1011448/necessary-uses-of-recursion-in-imperative-languages">“Necessary” Uses of Recursion in Imperative Languages</a></p></li>
  <li><p><a href="https://softwareengineering.stackexchange.com/questions/149167/are-functional-languages-better-at-recursion">Are functional languages better at recursion?</a></p></li>
  </ul>
  
  <p>This now becomes a teachable moment on a number of levels: imperative v. functional languages, recursion v. iteration, "expense" of function calls on the stack. Students appreciate being shown the messy truth behind topics that are sometimes treated reductively and simplistically. Let them wade in the mire and see what they think about these debates. Have them analyze the arguments they mind on here; now they are thinking on much higher, more sophisticated level about program design.</p>
  
  <p>The key line that I take away from all of these is this one: "You almost never use recursion for performance reasons. you use recursion to make the problem more simple" (top answer to the first post I linked to). <strong>It's often times an exercise in <em>thinking</em> more so than <em>programming</em>.</strong></p>
  
  <p>From a pragmatic perspective, discuss use cases for something like merge sort and quicksort (recursive) v. bubble sort (iterative). Throw in traversing tree structures as well. There is a time and a place for thinking recursively. Iteration is not always the best choice to make.</p>
  
  <p>Last, from an aesthetic perspective, based on my time studying SML, there is a beauty, an elegance, an aesthetic to a well-written recursive function. It's clean, clear, easy-to-understand. If part of code quality is its readability, then recursion has an aesthetic quality to it that a for-loop arguably does not.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-22T11:44:48.060Z
Answers.Text: Even experienced programmers have trouble with recursion. Even though TreeWalker + Visitor is a textbook pattern, I have a heck of a time getting programmers to trust it. The recursion seems to confuse them.
Answers.UserDisplayName: pojo-guy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:35:03.457Z
Answers.Text: I like this teachable moment, and I like reformulating the tool in their minds: an exercise in thinking more so than programming.
Answers.UserDisplayName: GermaneDork
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-01T04:31:53.687Z
Answers.Text: The answer is, like most things, "it depends".  +1 for traversing a tree structure.
Answers.UserDisplayName: pojo-guy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-28T13:22:19.267Z
Answers.Text: More specifically, the answer is "it's a tool, and like others, it does not fits everywhere"
Answers.UserDisplayName: Walfrat
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:32:12.567Z
Answers.LastActivityDate: 2017-06-07T05:32:12.567Z
Answers.UserDisplayName: Peter
Answers.Body: <p>When I teach recursion, even if I am not at a point in the curriculum where it is possible to introduce trees in coding problems, I always at least provide a high level discussion of trees, and the way that recursion is a natural way to process anything organized in a tree.</p>
  
  <p>Anyone that has worked with files and folders/directories on a computer is already familiar with a kind of tree.    Adding up the amount of disk space used, or the number of files, is naturally recursive.    Web pages, XML and JSON data are other very practical examples of data that has a tree shape and where we frequently use recursion, in practice, for real, to do processing.</p>
  
  <p>I tell my students that while a list or array can be processed either with a loop or with recursion, and its a choice as to which to use, 
  with a tree, its almost always much easier to write a recursive algorithm, and folks almost always do, in practice.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-07T21:17:32.607Z
Answers.Text: I'd go a step further and show them a non-recursive implementation of a tree traversal, or perhaps a merge sort, along with a recursive version.  Or if you *really* want to make the point, have them *write* both versions.
Answers.UserDisplayName: Ray
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T05:36:44.870Z
Answers.LastActivityDate: 2017-06-07T05:36:44.870Z
Answers.UserDisplayName: Phill Conrad
Answers.Body: <p>For any language/compiler that supports tail-call optimisation, there is no use of the stack for recursion. So you can implement <code>while True:</code> recursively. In these languages recursion is used more. In python it is used less, unless the depth is (as you said) O(log n). However the design may be easier done using recursion, and you can always convert recursion into iteration.</p>
  
  <p>Some languages/compilers that support tail call optimisation.</p>
  
  <ul>
  <li>C/gcc </li>
  <li>C++/gcc </li>
  <li>lisp/any </li>
  <li>Eiffel/some </li>
  <li>Prolog/any </li>
  <li>Scala/any — for direct tail calls (sometimes)</li>
  <li>Scheme/any</li>
  <li>JavaScript - ECMAScript 6.0</li>
  </ul>
  
  <p>some that don't</p>
  
  <ul>
  <li>Python/most</li>
  <li>C#/all</li>
  <li>VB.net/all</li>
  <li>Java</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-19T00:01:14.573Z
Answers.Text: "For any language/compiler that supports tail-call optimisation, there is no use of the stack for recursion." – That is only true if the recursive call is a tail call, i.e. for tail-recursive calls. Traversing a tree, for example, is *not* trivially tail-recursive, since you have a recursive call for every branch and there can be at most one tail-recursive call. (You *can* make it tail-recursive by introducing a stack which you manage yourself, of course.)
Answers.UserDisplayName: Jörg W Mittag
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-19T00:02:33.617Z
Answers.Text: Also, Scala does not support Proper Tail Calls. It only supports Direct Tail Recursion, i.e. Tail Recursion where a method *directly* calls itself in tail position. (And "directly calls itself" means that the method must be `final`, otherwise there would be no guarantee where the call is dynamically dispatched to!)
Answers.UserDisplayName: Jörg W Mittag
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T17:38:51.550Z
Answers.LastActivityDate: 2017-07-13T18:43:47.717Z
Answers.LastEditDate: 2017-07-13T18:43:47.717Z
Answers.UserDisplayName: ctrl-alt-delor
Answers.Body: <p>In addition to the other good answers already provided, I want to add that students should learn recursion because they will encounter it in real life. </p>
  
  <p>Any one of them who goes on to program for a living will at some point need to understand, maintain, or debug a recursive function. </p>
  
  <p>So they must be able to recognize recursion, understand how it works, see when it's broken, and know how to fix it.</p>
  
  <p>It <em>is</em> generally agreed that looping is better than recursing - <em>when</em> you can actually get the job done with a loop. But there are times when it is far easier to crack the nut with recursion rather than a loop. And as a programmer, you must be armed for those times.</p>
  
  <p>Besides, recursion is cool. :-D</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-12T21:47:03.633Z
Answers.Text: Playing the (recursion-hating) devil's advocate here, I'd argue that this argument of "Any one of them ... will at some point need to ... so they must be able to ..." leads to somewhat of a vicious cycle - adding esoteric concepts to the syllabus encourages practitioners to utilizing such (and additional) esoteric concepts in production code, even at detriment to readability and maintainability, which in turn would require making CS degrees even harder. It's complex enough as is, and I'd be concerned about CS degrees striving to make grads prepared for any eventuality. But recursion is cool :)
Answers.UserDisplayName: yoniLavi
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T15:57:32.687Z
Answers.LastActivityDate: 2017-06-07T17:54:18.070Z
Answers.LastEditDate: 2017-06-07T17:54:18.070Z
Answers.UserDisplayName: G. Ann - SonarSource Team
Answers.Body: <p>An introductory programming class is a good place to familiarize students with some real-world issues in programming apart from the more popular ones. Using recursion is just one example of how they might address them.</p>
  
  <p>Programming for the long haul (whether it's for production or to support one's own research, for example) is not always about obtaining the best performance in terms of computer resource use.</p>
  
  <p>Recursion is just one example of how to overcome a programming obstacle in order to satisfy an immediate objective. In cases where the most intuitive understanding of a problem is in terms of recursion, then there are reasons to use recursion:</p>
  
  <ul>
  <li>Software maintainability requires writing code that can be understood by follow-on developers. Recursion may represent the easiest formulation that makes that piece of software understandable so that it can be maintained at some later date.</li>
  <li>Even if you know there is a more resource efficient way to do something, there might not be time to implement it to completion and still meet the immediate needs of a project. Recursion might be an expeditious way to move forward.</li>
  <li>There may be bigger coding challenges in other areas, and spending time optimizing now when it can be done later might result in these bigger problems being completely missed, causing serious consequences.</li>
  </ul>
  
  <p>So recursion becomes another tool that helps a programmer get where he needs to be in terms of function and maintainability. Once those two factors have been addressed, then, if time and budget permits, then the software can be optimized in other areas (hopefully why still being functional AND maintainable).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-13T02:29:41.920Z
Answers.Text: Nice perspective.  Welcome to [cseducators.se]!  I hope we hear more from you in the future. :)
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-13T00:28:56.977Z
Answers.LastActivityDate: 2017-07-13T00:28:56.977Z
Answers.UserDisplayName: Jim
Answers.Body: <p>Having a discussion about the plusses and minuses can be valuable, but sometimes what you need is a motivating example. It's true that loops and recursion are equivalent in the sense that they can provably accomplish the same tasks.  However, some problems are simply astoundingly easier with recursion, such as iterating through a tree, or finding all of the anagrams of a set of letters.  I mention this second example because it can be brought up in a introductory class long before trees come into the picture.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-07T10:35:28.810Z
Answers.LastActivityDate: 2017-06-07T10:35:28.810Z
Answers.UserDisplayName: Ben I.
Answers.Body: <p>The practical interest of recursion is obvious to the students when they are presented with problems where the underlying data structure is, for example,  tree.</p>
  
  <p>For exemple : figures that can be circles, squares, or group of figures.  Or directories containing files and directories.   XML nodes, etc. Recursive descent to evaluate an expression...</p>
  
  <p>They don't even ask how to process them by iterative programs. Obviously good (and best) practice.</p>
  
  <p>The classical examples about numbers are counterproductive : factorial, fibonacci, etc. as the students (mostly) already know instantly how to express them with loops. So why should they spend efforts learning how to do it painfully a "less natural" way ? </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-20T20:45:12.193Z
Answers.LastActivityDate: 2017-07-20T21:04:10.873Z
Answers.LastEditDate: 2017-07-20T21:04:10.873Z
Answers.UserDisplayName: Michel Billaud
Body: <p>Context: CS1-style, intro programming class, using an interpreted language (Python).</p>
  
  <p>I will get a hand raised asking "Why are we learning recursion? Is it good programming practice?"</p>
  
  <p>My response is typically:</p>
  
  <ul>
  <li>We are learning recursion since reducing problems into smaller problems is a key skill, and recursion is just an example of reducing a problem to a self-similar smaller problem.</li>
  <li>Also, no, recursion not universally better design. Often, calling functions repeatedly like this wastes space on the stack and the implementation can be much less efficient. Our recursive formulation of factorial for example, is a terrible design. Unless you know the recursion depth is bound by something small (think: logarithmic) and resultant implementation is much simpler, then its not worth it.</li>
  </ul>
  
  <p>Students seem deflated with that response. Why learn something that is not very practical, or is often inefficient? Why learn something that is 'sometimes simpler' when (to them) it seems actually like a counter-intuitive design?</p>
  
  <p>My question(s): how do I get students excited about recursion? How do I better motivate studying recursion? Can I better / more naturally express those conditions under which (or those languages for which) recursion is not a poor design choice?</p>
  
  <p>This is challenging once you accept that CS1 students likely: know nothing about functional languages, where recursion is more natural; don't know anything about side-effect free design or mathematical proofs of correctness; are not using recursive data structures yet; etc. It feels like the 'benefits' of recursion are hard to express to a CS0/CS1 audience.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-07T05:29:16.890Z
Comments.Text: I cannot express how much I like this question. I see students struggling with this.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-07T11:52:29.507Z
Comments.Text: I don't quite have an answer, but I think that lies somewhere along the path of 'what would they be missing if you didn't need to teach recursion'.
Comments.UserDisplayName: Sean Houlihane
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-13T18:36:38.100Z
Comments.Text: One moment, I will tackle the first part by asking someone, and get back to you with the answer.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-13T18:39:19.460Z
Comments.Text: This looks like a case for “That is a rely good question. Can you tell me what makes recursion good, and what makes recursion bad?”
Comments.UserDisplayName: ctrl-alt-delor
Tags: <lesson-ideas><student-motivation><recursion>
Title: How to respond when students ask "is recursion good practice"?
ThreadText: # How to respond when students ask "is recursion good practice"?
  
  (Asked by: username_0 on 2017-06-07)
  
  Context: CS1-style, intro programming class, using an interpreted language (Python).
  
  I will get a hand raised asking "Why are we learning recursion? Is it good programming practice?"
  
  My response is typically:
  
  * We are learning recursion since reducing problems into smaller problems is a key skill, and recursion is just an example of reducing a problem to a self-similar smaller problem.
  * Also, no, recursion not universally better design. Often, calling functions repeatedly like this wastes space on the stack and the implementation can be much less efficient. Our recursive formulation of factorial for example, is a terrible design. Unless you know the recursion depth is bound by something small (think: logarithmic) and resultant implementation is much simpler, then its not worth it.
  
  Students seem deflated with that response. Why learn something that is not very practical, or is often inefficient? Why learn something that is 'sometimes simpler' when (to them) it seems actually like a counter-intuitive design?
  
  My question(s): how do I get students excited about recursion? How do I better motivate studying recursion? Can I better / more naturally express those conditions under which (or those languages for which) recursion is not a poor design choice?
  
  This is challenging once you accept that CS1 students likely: know nothing about functional languages, where recursion is more natural; don't know anything about side-effect free design or mathematical proofs of correctness; are not using recursive data structures yet; etc. It feels like the 'benefits' of recursion are hard to express to a CS0/CS1 audience.
  
  **Tags:** lesson-ideas, student-motivation, recursion
  
  > **Comments:**
  > **username_1**: I cannot express how much I like this question. I see students struggling with this.  
  > **username_2**: I don't quite have an answer, but I think that lies somewhere along the path of 'what would they be missing if you didn't need to teach recursion'.  
  > **username_3**: One moment, I will tackle the first part by asking someone, and get back to you with the answer.  
  > **username_3**: This looks like a case for “That is a rely good question. Can you tell me what makes recursion good, and what makes recursion bad?”  
  
  ---
  
  ## 11 answers
  
  ### Answer by username_8 on 2017-06-07. Score: 20 | Accepted answer
  
  Quite honestly, I would be upfront with them about the debate. Send them to a couple other SE threads:
  
  * [Efficiency: recursion vs loop](https://stackoverflow.com/questions/9386375/efficiency-recursion-vs-loop)
  * [“Necessary” Uses of Recursion in Imperative Languages](https://stackoverflow.com/questions/1011448/necessary-uses-of-recursion-in-imperative-languages)
  * [Are functional languages better at recursion?](https://softwareengineering.stackexchange.com/questions/149167/are-functional-languages-better-at-recursion)
  
  This now becomes a teachable moment on a number of levels: imperative v. functional languages, recursion v. iteration, "expense" of function calls on the stack. Students appreciate being shown the messy truth behind topics that are sometimes treated reductively and simplistically. Let them wade in the mire and see what they think about these debates. Have them analyze the arguments they mind on here; now they are thinking on much higher, more sophisticated level about program design.
  
  The key line that I take away from all of these is this one: "You almost never use recursion for performance reasons. you use recursion to make the problem more simple" (top answer to the first post I linked to). **It's often times an exercise in *thinking* more so than *programming*.**
  
  From a pragmatic perspective, discuss use cases for something like merge sort and quicksort (recursive) v. bubble sort (iterative). Throw in traversing tree structures as well. There is a time and a place for thinking recursively. Iteration is not always the best choice to make.
  
  Last, from an aesthetic perspective, based on my time studying SML, there is a beauty, an elegance, an aesthetic to a well-written recursive function. It's clean, clear, easy-to-understand. If part of code quality is its readability, then recursion has an aesthetic quality to it that a for-loop arguably does not.
  
  > **Comments:**
  > **username_0**: I like this teachable moment, and I like reformulating the tool in their minds: an exercise in thinking more so than programming.  
  > **username_9**: The answer is, like most things, "it depends".  +1 for traversing a tree structure.  
  > **username_10**: More specifically, the answer is "it's a tool, and like others, it does not fits everywhere"  
  > **username_9**: Even experienced programmers have trouble with recursion. Even though TreeWalker + Visitor is a textbook pattern, I have a heck of a time getting programmers to trust it. The recursion seems to confuse them.  
  
  ---
  
  ### Answer by username_11 on 2017-06-07. Score: 15
  
  When I teach recursion, even if I am not at a point in the curriculum where it is possible to introduce trees in coding problems, I always at least provide a high level discussion of trees, and the way that recursion is a natural way to process anything organized in a tree.
  
  Anyone that has worked with files and folders/directories on a computer is already familiar with a kind of tree. Adding up the amount of disk space used, or the number of files, is naturally recursive. Web pages, XML and JSON data are other very practical examples of data that has a tree shape and where we frequently use recursion, in practice, for real, to do processing.
  
  I tell my students that while a list or array can be processed either with a loop or with recursion, and its a choice as to which to use,
  with a tree, its almost always much easier to write a recursive algorithm, and folks almost always do, in practice.
  
  > **Comments:**
  > **username_12**: I'd go a step further and show them a non-recursive implementation of a tree traversal, or perhaps a merge sort, along with a recursive version.  Or if you *really* want to make the point, have them *write* both versions.  
  
  ---
  
  ### Answer by username_3 on 2017-06-07. Score: 4
  
  For any language/compiler that supports tail-call optimisation, there is no use of the stack for recursion. So you can implement `while True:` recursively. In these languages recursion is used more. In python it is used less, unless the depth is (as you said) O(log n). However the design may be easier done using recursion, and you can always convert recursion into iteration.
  
  Some languages/compilers that support tail call optimisation.
  
  * C/gcc
  * C++/gcc
  * lisp/any
  * Eiffel/some
  * Prolog/any
  * Scala/any — for direct tail calls (sometimes)
  * Scheme/any
  * JavaScript - ECMAScript 6.0
  
  some that don't
  
  * Python/most
  * C#/all
  * VB.net/all
  * Java
  
  > **Comments:**
  > **username_6**: "For any language/compiler that supports tail-call optimisation, there is no use of the stack for recursion." – That is only true if the recursive call is a tail call, i.e. for tail-recursive calls. Traversing a tree, for example, is *not* trivially tail-recursive, since you have a recursive call for every branch and there can be at most one tail-recursive call. (You *can* make it tail-recursive by introducing a stack which you manage yourself, of course.)  
  > **username_6**: Also, Scala does not support Proper Tail Calls. It only supports Direct Tail Recursion, i.e. Tail Recursion where a method *directly* calls itself in tail position. (And "directly calls itself" means that the method must be `final`, otherwise there would be no guarantee where the call is dynamically dispatched to!)  
  
  ---
  
  ### Answer by username_13 on 2017-06-07. Score: 4
  
  In addition to the other good answers already provided, I want to add that students should learn recursion because they will encounter it in real life.
  
  Any one of them who goes on to program for a living will at some point need to understand, maintain, or debug a recursive function.
  
  So they must be able to recognize recursion, understand how it works, see when it's broken, and know how to fix it.
  
  It *is* generally agreed that looping is better than recursing - *when* you can actually get the job done with a loop. But there are times when it is far easier to crack the nut with recursion rather than a loop. And as a programmer, you must be armed for those times.
  
  Besides, recursion is cool. :-D
  
  > **Comments:**
  > **username_14**: Playing the (recursion-hating) devil's advocate here, I'd argue that this argument of "Any one of them ... will at some point need to ... so they must be able to ..." leads to somewhat of a vicious cycle - adding esoteric concepts to the syllabus encourages practitioners to utilizing such (and additional) esoteric concepts in production code, even at detriment to readability and maintainability, which in turn would require making CS degrees even harder. It's complex enough as is, and I'd be concerned about CS degrees striving to make grads prepared for any eventuality. But recursion is cool :)  
  
  ---
  
  ### Answer by username_15 on 2017-07-13. Score: 4
  
  An introductory programming class is a good place to familiarize students with some real-world issues in programming apart from the more popular ones. Using recursion is just one example of how they might address them.
  
  Programming for the long haul (whether it's for production or to support one's own research, for example) is not always about obtaining the best performance in terms of computer resource use.
  
  Recursion is just one example of how to overcome a programming obstacle in order to satisfy an immediate objective. In cases where the most intuitive understanding of a problem is in terms of recursion, then there are reasons to use recursion:
  
  * Software maintainability requires writing code that can be understood by follow-on developers. Recursion may represent the easiest formulation that makes that piece of software understandable so that it can be maintained at some later date.
  * Even if you know there is a more resource efficient way to do something, there might not be time to implement it to completion and still meet the immediate needs of a project. Recursion might be an expeditious way to move forward.
  * There may be bigger coding challenges in other areas, and spending time optimizing now when it can be done later might result in these bigger problems being completely missed, causing serious consequences.
  
  So recursion becomes another tool that helps a programmer get where he needs to be in terms of function and maintainability. Once those two factors have been addressed, then, if time and budget permits, then the software can be optimized in other areas (hopefully why still being functional AND maintainable).
  
  > **Comments:**
  > **username_16**: Nice perspective.  Welcome to [cseducators.se]!  I hope we hear more from you in the future. :)  
  
  ---
  
  ### Answer by username_16 on 2017-06-07. Score: 4
  
  Having a discussion about the plusses and minuses can be valuable, but sometimes what you need is a motivating example. It's true that loops and recursion are equivalent in the sense that they can provably accomplish the same tasks. However, some problems are simply astoundingly easier with recursion, such as iterating through a tree, or finding all of the anagrams of a set of letters. I mention this second example because it can be brought up in a introductory class long before trees come into the picture.
  
  
  ---
  
  ### Answer by username_17 on 2017-07-20. Score: 2
  
  The practical interest of recursion is obvious to the students when they are presented with problems where the underlying data structure is, for example, tree.
  
  For exemple : figures that can be circles, squares, or group of figures. Or directories containing files and directories. XML nodes, etc. Recursive descent to evaluate an expression...
  
  They don't even ask how to process them by iterative programs. Obviously good (and best) practice.
  
  The classical examples about numbers are counterproductive : factorial, fibonacci, etc. as the students (mostly) already know instantly how to express them with loops. So why should they spend efforts learning how to do it painfully a "less natural" way ?
  
  
  ---
  
  ### Answer by username_4 on 2017-07-20. Score: 1
  
  > "Why are we learning recursion? Is it good programming practice?"
  
  Most things in programming should be thought of as **tools**. Languages are tools. Algorithms are tools. Various approaches are tools.
  
  Different tools are for different jobs. A carpenter learns about a hammer, a saw, a wrench, etc because sometimes the hammer will be the best tool for the job, sometimes it'll be the saw, and sometimes it'll be the wrench. Sometimes, the best tool will be something the carpenter has never used before! But the more tools they already know, the easier it'll be to learn about new tools. Having learned about a wrench makes it easier to learn about a screwdriver when you need to. So learning about a tool is never wasted time: even if we don't use the tool every day, it helps us learn about stuff we need to know.
  
  That's why we learn about a bunch of different things in programming. Sometimes a loop will be the best tool. Sometimes a recursive function will be the best tool. Sometimes we'll even come across new ideas and approaches! And we can use the tools we've already learned about to help learn about these new tools.
  
  So even if recursion doesn't solve every problem (just like a hammer doesn't cover everything a carpenter has to do), it's still worth learning about because it adds a tool to our toolbelt.
  
  
  ---
  
  ### Answer by username_5 on 2017-06-07. Score: 1
  
  A professional programmer could go most of her or his career without having to resort to it. The pros, some problems/algorithms are just not very tractable outside of a recursive approach (I usually assign the flood fill algorithm in my AP or post-AP classes). These tend to be rare. Cons, very prone to error, the algorithms may not be particularly intuitive and in most cases can be replaced with an iterative approach. Besides Flood Fill, the recursive solution to the Tower of Hanoi problem is another powerful illustration of how powerful a recursive algorithm can be.
  
  > **Comments:**
  > **username_1**: *This doesn't exactly answer the question.* The question was about getting students to be excited about recursion, as well as other things that are specifically written in the question.  
  
  ---
  
  ### Answer by username_1 on 2017-06-07. Score: 1
  
  I feel it is very bad to say "no, don't ever use this".
  
  For recursion, the second most important detail is to have an `exit statement`. That is the condition upon which the recursion terminates. So long as the exit statement is good, recursion is a very, very powerful tool.
  
  ```
  def thing(position, str):
      if position == 0:
          print(str)
          return str
      else:
          print("single letters: "+thing(position-1, str[:,position]))
          return thing(position-1, str[:,position])
  
  ```
  
  This has a well defined exit statement, that will be met, because every call decreases `position` by 1, and the exit checks if `position` is 0. Which eventually happens for any positive integer value being decremented.
  
  This shows that recursion is very useful, BUT it **must** have a good exit statement. So saying "it's horrible in any programming language" is *very* misleading.
  
  So in essence, the main point is showing how important choosing a good exit statement is. It has to be one that must be met, simply because of the recursive action (in the example, the `position-1` parameter being passed, and the `position==0` check).
  
  NOTE: this is code adapted from java, so it might have inaccuracies. Feel free to correct them.
  
  > **Comments:**
  > **username_0**: I agree that "it's horrible in any programming language" is misleading, but they don't know about functional languages and, as a CS1 class, its hard to appreciate side-effect free design. I fear the nuances of when recursion is a good design choice is hard to describe in CS1. (Your observation about an 'exit' statement is essentially 'you need a base case' and is something we cover and not, itself, answer to "when is recursion good practice?"). I'll revise my question to be clearer.  
  > **username_1**: @username_0 yes. As I said, you should explain the importance of good exit statements. Ones that must happen, to avoid a stackoverflow,  
  > **username_1**: @username_0 oh. Well then I'll revise my answer, for future readers  
  > **username_6**: You don't need a base case. `def receive(event): process(event); receive(eventstream.next); end` is a perfectly good way of writing an operating system, for example. Operating systems don't have a base case, they should *never* stop.  
  
  ---
  
  ### Answer by username_7 on 2017-06-07. Score: 0
  
  To answer this question I would say it depends on the context. For something such as Quick sort then yes, however if recursion could be replaced by iterating a function call then it is often easier for a programmer to identify a particular point in a program and where it has been executed (useful for debugging). It all depends on the level of confidence in the programmer, and the actual requirement for recursion to solve the problem.
  
  > **Comments:**
  > **username_1**: Could you please clarify or add details to the questions asked?  e.g.: *"My question(s): how do I get students excited about recursion? How do I better motivate studying recursion? Can I better / more naturally express those conditions under which (or those languages for which) recursion is not a poor design choice?"*  
  
  ---
  
  