Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
This question is pretty similar to programmers.stackexchange.com/questions/24997/… which was also asked today. Some good answers there. –  NickC Dec 10 '10 at 5:04
1  
How can you be an average programmer if you do not understand recursion? (note the difference from "any programmer") –  user1249 Jun 6 '11 at 7:06
add comment

7 Answers

up vote 14 down vote accepted

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

share|improve this answer
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 9: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
add comment

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.

share|improve this answer
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. –  heretik Dec 10 '10 at 3:42
add comment

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.

share|improve this answer
    
+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. (programmers.stackexchange.com/questions/20036/… which you have already read) –  Orbling Dec 10 '10 at 9:21
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
True (and +1), but, of course, someone has to write the abstraction. –  Lawrence Dol Dec 10 '10 at 5: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 9:23
    
+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
add comment

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!

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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