25
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I cannot express how much I like this question. I see students struggling with this. $\endgroup$ – ItamarG3 Jun 7 '17 at 5:29
  • 1
    $\begingroup$ 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'. $\endgroup$ – Sean Houlihane Jun 7 '17 at 11:52
  • $\begingroup$ One moment, I will tackle the first part by asking someone, and get back to you with the answer. $\endgroup$ – ctrl-alt-delor Jul 13 '17 at 18:36
  • $\begingroup$ 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?” $\endgroup$ – ctrl-alt-delor Jul 13 '17 at 18:39

13 Answers 13

16
$\begingroup$

Quite honestly, I would be upfront with them about the debate. Send them to a couple other SE threads:

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.

$\endgroup$
  • 2
    $\begingroup$ I like this teachable moment, and I like reformulating the tool in their minds: an exercise in thinking more so than programming. $\endgroup$ – GermaneDork Jun 7 '17 at 5:35
  • 1
    $\begingroup$ The answer is, like most things, "it depends". +1 for traversing a tree structure. $\endgroup$ – pojo-guy Jul 1 '17 at 4:31
  • 2
    $\begingroup$ More specifically, the answer is "it's a tool, and like others, it does not fits everywhere" $\endgroup$ – Walfrat Aug 28 '17 at 13:22
  • $\begingroup$ 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. $\endgroup$ – pojo-guy Sep 22 '18 at 11:44
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ray Aug 7 '17 at 21:17
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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
$\endgroup$
  • 3
    $\begingroup$ "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.) $\endgroup$ – Jörg W Mittag Jun 19 '17 at 0:01
  • 3
    $\begingroup$ 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!) $\endgroup$ – Jörg W Mittag Jun 19 '17 at 0:02
3
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

When teaching students who are old enough or invested enough to care about performance (the younger ones typically do not), I introduce it like this:

"We can either make code that's easy for us to write, or easy for the computer to execute. You choose. If you're feeling lazy, and performance isn't an issue, recursion is perfect: you will finish writing it sooner, and you'll have fewer bugs. If you're working on a performance-critical problem, use loops: they are much faster and more efficient for the computer, and although it'll take you more effort to write, it might make the difference between "fast enough" and "too slow to be useful""

I also add:

"In computer game development, more than half of what you see is fake. The skill is in deciding what things you can fake and the player/user will never notice, versus the things you have to do correctly or else they will see the gaps and be disappointed"

(there are many rich media examples of game-development hacks that have been exposed and been written about. E.g. search for "game glitches", "game programming hacks", etc. My go-to example at the moment is to pick images from this article: http://www.gamesradar.com/you-think-fallout-train-hack-was-bad-your-games-are-made-lies/ )

$\endgroup$
  • $\begingroup$ Recursion is only slow if your language/compiler does not have tail call optimisation. see my answer for more info. $\endgroup$ – ctrl-alt-delor Jun 7 '17 at 17:42
  • $\begingroup$ @richard Sure. I was assuming the question was valid, that the situation was one where recursion was demonstrably or predictably likely to be slower, and where there's a need to illustrate the reasoning process for the programmer, showing why we still need both approaches. $\endgroup$ – user31 Jun 7 '17 at 18:11
  • 1
    $\begingroup$ I disagree with the premise that finishing sooner or having poor performance equates with being lazy. There are other factors to consider in writing production software or eave "useful" software, for that matter. $\endgroup$ – Jim Jul 12 '17 at 23:50
  • $\begingroup$ I didn't equate them. Although I do encourage laziness when writing software - it generally achieves a better outcome for all concerned (except the computer, but I'm happy to wear out a few billion transistors a fraction of a century sooner) $\endgroup$ – user31 Jul 14 '17 at 2:45
2
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – GermaneDork Jun 7 '17 at 5:24
  • $\begingroup$ @GermaneDork yes. As I said, you should explain the importance of good exit statements. Ones that must happen, to avoid a stackoverflow, $\endgroup$ – ItamarG3 Jun 7 '17 at 5:25
  • $\begingroup$ @GermaneDork oh. Well then I'll revise my answer, for future readers $\endgroup$ – ItamarG3 Jun 7 '17 at 5:40
  • $\begingroup$ 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. $\endgroup$ – Jörg W Mittag Jun 19 '17 at 0:04
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ItamarG3 Jun 7 '17 at 16:21
1
$\begingroup$

"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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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?" $\endgroup$ – ItamarG3 Jun 7 '17 at 9:32
0
$\begingroup$

Yes, Recursion is good practice.
Many problem statements are recursive in essence: the best, most concise, clear and provably correct way to state the problem uses a recursive reference. But a recipe is not the meal, so to speak, and how we solve a problem can be different from how it is stated. It is often necessary to find a way to restate the problem into iterative terms.

Induction restates something into a base case, a "case for N" and a statement about how to go to "N + 1". This is how recursion can be transformed into iteration, usually by identifying invariants.

These are all vitally important to being able to analyze and eventually code any inductive or recursive problem. It is necessary to see it in different ways to get at the best solution. So, the practice makes for a more perfect solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.