8

I've read several books and learned through experience that optimizing code to the point where it is inscrutable, or coming up with an extremely fast but extremely complex solution to a problem is not desirable when working in teams, or even when you're working by yourself and have to understand your clever solution some time later.

My question is, should recursion be treated in the same manner? Does the average programmer understand recursion easily and thus one should use it with impunity, or does the average programmer not understand recursion very well and one should stay away from it for the sake of overall team productivity?

I know there are simple answers of, "Any programmer who doesn't understand recursion isn't worth a grain of salt, so don't worry about them" but I was wondering if you all had some real world experience you would like to share that would illuminate the issue more than the opinion I just mentioned.

Macy Abbey
  • 667
  • 1
  • 7
  • 15
  • 2
    This question is pretty similar to http://programmers.stackexchange.com/questions/24997/can-all-the-recursive-functions-be-coded-with-iterations which was also asked today. Some good answers there. – Nicole Dec 10 '10 at 05:04
  • 5
    How can you be an average programmer if you do not understand recursion? (note the difference from "any programmer") –  Jun 06 '11 at 07:06

7 Answers7

42

Some problems are naturally recursive. Coming up with an iterative solution in these cases can actually be more clunky and complex than recursive ones. A good example is any algorithm which needs to traverse a hierarchical tree structure, which is a not-uncommon task in programming.

TL;DR version: No.

Bobby Tables
  • 20,516
  • 7
  • 54
  • 79
  • 9
    Agreed. It's more dangerous to label things as "harmful" and go to extremes to avoid them - which will always end up being more confusing and hard to maintain going forwards. – bly Dec 10 '10 at 03:42
21

Does the average programmer understand recursion easily and thus one should use it with impunity, or does the average programmer not understand recursion very well and one should stay away from it for the sake of overall team productivity?

I'd say that the average programmer understands recursion perfectly. Indeed, if the programmer has done a degree in Computer Science or Software Engineering it is pretty much guaranteed. Granted, there are some very below average programmers out there, but you don't want them on your team.

In this case, the distinction between an average and a good programmer is knowing when to use recursion and when not to. And that depends on the problem being solved AND the language being used to solve it.

  • If you are using a functional programming language, recursion is a natural and efficient solution for a wide range of problems. (Tail recursion optimization rules!)

  • If you are using an OO or plain procedural language, recursion can be inefficient and can be problematic due to stack overflows. So in some cases you would choose an iterative solution rather than a recursive one. However, in other cases, the recursive solution is so much more simple and elegant that the (possibly more efficient) iterative solution would be the "too clever" one. (For example, if the problem requires backtracking, building or walking trees / graphs, etc, recursion is often simpler.)

Stephen C
  • 25,180
  • 6
  • 64
  • 87
  • 1
    +1 For tail recursion comment. Often an attempt to remove recursion ends up with a lot of stack structures and loops in your code, which effectively replicate the call-stack component. – Orbling Dec 10 '10 at 09:26
  • 1
    @Orbling - that is true, but a stack implemented using an array or arraylist is likely to be more scalable than a thread's call stack. Especially since thread call stacks can't grow in many language implementations. – Stephen C Mar 21 '13 at 13:50
  • Aye, it is an eternal problem of recursive function design. More an issue for the language designers to address than the programmer, ideally. – Orbling Mar 22 '13 at 14:36
  • "*Granted, there are some very below average programmers out there*": OK, it just has to be said... By very definition half the programmers out there are below average and half of those are "very below" average. – Lawrence Dol Feb 19 '15 at 02:00
  • @LawrenceDol - I've never seen someone claim that "very" means half of anything. What is your source for your definition? (This also has to be asked, because pedantry only has *any* value if it is factually based.) – Stephen C Feb 28 '15 at 07:13
  • @Stephen C: Chillax man; you missed the point. Even if every programmer in the world was a certified genius, half of them would still be below average. And some significant percentage of *them* would be arguably very below average. – Lawrence Dol Feb 28 '15 at 20:53
  • @LawrenceDol - Sorry. Once again you inferring a meaning that I did not mean into something that I said. I DID NOT mean that a significant percentage of programmers don't understand recursion. That is the real point. – Stephen C Mar 02 '15 at 13:42
11

Recursion is a foundational principle in most functional programming languages. Iteration (looping) in functional languages is usually accomplished via recursion.

Functional languages have seen somewhat of a renaissance lately, due to the need to elegantly handle more processor cores; functional languages help achieve this kind of concurrency by providing ways to better reason about your program without the complexity involved in locking mutable structures.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
  • +1 Good comment. Though I'm not sure "a renaissance" is entirely right, or the reason of multi-cores. They have always been a favourite paradigm of those that knew about them, but their proliferation in to the mainstream was never great. Functional languages have just become more mainstream, would take a whole thread to go over that issue mind. (http://programmers.stackexchange.com/questions/20036/why-the-current-enthusiasm-for-functional-programming/20143#20143 which you have already read) – Orbling Dec 10 '10 at 09:21
11

Some problems, such as walking a tree structure (walking, say, an entire directory structure, as opposed to, say, searching for a specific B-Tree node), are ideally suited to using recursion; the non-recursive equivalents often simply add the complication of managing your own stack.

In these cases, recursion is the best, simplest solution and easiest to understand.

Lawrence Dol
  • 261
  • 1
  • 9
7

I would say use recursion where it's appropriate, but always seek out ways to avoid explicit recursion.

For example, if you find the need to manually traverse a tree structure, then yes, you should be using recursion. If someone's dumb enough to not understand a recursive tree traversal, they're going to make neither head nor tail of the iterative version.

But a better option is to use an iterator that abstracts the recursion away to the point where all you see is "I perform this operation on everything in the tree".

Anon.
  • 2,195
  • 15
  • 14
  • 1
    True (and +1), but, of course, someone has to write the abstraction. – Lawrence Dol Dec 10 '10 at 05:02
  • 1
    As @Software Monkey says, still should usually be coded recursively, but abstraction to an iterator for "use" is fine. – Orbling Dec 10 '10 at 09:23
  • 1
    +1 for the point that someone who wouldn't understand the recursive version most likely won't understand the iterative version. Unfortunately, that person also wouldn't realize that he doesn't understand the iterative version. – Larry Coleman Dec 10 '10 at 16:47
3

Recursion, is the simplest mechanism from a code cleanliness standpoint. If speed is absolutely of the essence, then perhaps you can use a 2D array of problem parameters. Spawning a daughter process is then simply appending another item to the array. I once did an assembler tridiagonal solver, that was a big deal back in the day. The context needed per instance was 8 words per level, and each subproblem was a third the size of the previous. This "library" was only popular because it beat the heck out of all the other implementations out there. But, that's a pretty rare situation in programming, so you needn't succumb to "premature optimization", just because this solution is available. Obviously for a few things its terrible overkill, like the recursion 101 example "compute the factorial". But for most apps, it is a really elegant way to eliminate source code complexity.

I have a simple spell-checker I use for an app, (where I want to give hints about correcting minor misspellings), where I compute the "distance" between two strings, allowing deletions and additions are allowed. This leads to a potentially large tree structure, and the branches are trimmed as we only care about close matches. With recursion, its maybe twenty lines of code (I have both Fortran and C versions). I think it would be messy otherwise. Heck it was much easier to program/debug verify, than it was to think about that tree!

ChrisF
  • 38,878
  • 11
  • 125
  • 168
Omega Centauri
  • 1,038
  • 5
  • 8
0

I understand it but I have never explicitly used it. I think anyone that calls themselves a programmer should know or learn what it is as much as they need to know what the stack and heap are. Hey, everyone needs to know how min/max works on tic-tac-toe, via fancy recursion.

johnny
  • 3,669
  • 3
  • 21
  • 35