How to respond when students ask "is recursion good practice"?

Question

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.

Answer 1

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

• Efficiency: recursion vs loop

• “Necessary” Uses of Recursion in Imperative Languages

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

Answer 2

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.

Answer 3

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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 9

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.

Answer 10

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.

Answer 11

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

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.

Answer 13

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.