The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

recursive

Writing recursive algorithms was said to be a big no-no although the code ends up shorter, and create more elegant solutions.

Should I really stay away from recursive solutions? I would like to hear some comments from people who have real-world experience using or not using recursive algorithms.

Thanks
resursion
Tuesday, January 24, 2006
 
 
I'm curious as to why recursion is viewed as a no-no?

If you have a set task that needs to be repeated on an item in the dataset it is operating on, how else would you go about it, without having a limit of N to the number of nests that the function could read?

For example, I use recursion in my directory search algorithm. If I find a directory within a directory, sure, I could call another function, but I find it easier to just call the analyze function again on the new directory.

Granted, it does take code to a level of abstraction that some people have problems with, bt if you know what you are doing, you should be fine.
Josh McFarlane Send private email
Tuesday, January 24, 2006
 
 
I think the reason was you exercise the stack quite a bit, system resource, hard to debug... Like you said, the directory search problem is screaming for a recursive algorithm. Sometimes it is not easy to convert a naturally recursive algorithm to a linear one. I am wondering if I should even care to try.
resursion
Tuesday, January 24, 2006
 
 
I don't see it as a big no-no but the obvious problem with it is using up stack memory in extremely deep searches.  The answer for this is tail recursion.

Other than that I don't know of any issues and generally it produces a much more elegant result when done correctly.
Mark Flory Send private email
Tuesday, January 24, 2006
 
 
I never considered recursion elegant at all. It is only "elegant" to academics. Please avoid it.
Anon and anon
Tuesday, January 24, 2006
 
 
Aside from the potential performance penalties and limitations mentioned above, recursion is another of those things that I think can easily be abused, like multiple inheritance.  I've seen plenty of problems hammered into recursive solutions when much simpler solutions would have done the trick, though that kind of stuff seems much less pervasive in recent years for some reason.

That said, there are other problems that are just naturally recursive, so I think it's a mistake to go to the opposite extreme and try to eliminate recursion completely.  Certainly many operations on graphs or trees are best served when they are coded up recursively.
anon Send private email
Tuesday, January 24, 2006
 
 
" I never considered recursion elegant at all. It is only "elegant" to academics. Please avoid it."

Anon, how would you implement, for instance, a binary search tree? Would your iterative implementation really be more elegant than the natural recursive approach?
clcr
Tuesday, January 24, 2006
 
 
Recursion is fine.  The key bit of advice that floats around is that some problems can be solved both recursively and iteratively and not to use the former if the latter is viable.  Performance might certainly be a consideration but I'd think the biggest benefit is that more programmers would be able to grok the iterative solution.

Michael Abrash wrote a lot about this when he worked at id Software on the first Quake.  There were a lot of algorithms that he and John tended to implement recursively but they found out later that a natural iterative approach existed.  In the end the code was cleaner and easier to understand.  I think performance was equivalent, if I remember correctly.  The problem he was writing about, I believe, was scanline span determination from a BSP tree.
A programmer near the end
Tuesday, January 24, 2006
 
 
>I never considered recursion elegant at all. It is >only "elegant" to academics. Please avoid it.

I made a blanket statement...I really meant that I found it more elegant.  Which is also wrong because I meant simpler to understand, simpler to read (again to me).

Of course you made a blanket statement or two of your own.

Last I checked I am not, nor have I ever been, an academic.
Mark Flory Send private email
Tuesday, January 24, 2006
 
 
Nothing wrong with recursion.

If you need it.

If it's possible to rewrite a recursive algorithm as a while loop, I generally prefer to do so. But some algorithms can't be rewritten as a loop (or they become very very ugly when written as such) and in those cases, recursion is perfectly fine.

But when writing recursive algorithms, it's important to develop unit tests that stretch the limits of the stack. Certain recursive algorithms (qsort) have degenerate cases that will cause the stack to overflow. PUtting those degenerate cases into unit tests helps ensure that you'll modify your algorithm to prevent the stack from overflowing.
BenjiSmith Send private email
Tuesday, January 24, 2006
 
 
The problem with "recursion" is that some people tend to use it as a 'magic bullet' on problems.  Don't know the depth of your directory structure?  No problem, recursion will handle it.

Don't know the depth of your binary tree you want to search?  No problem, recursion will handle it.

The problems with 'magic bullet' solutions is when they break down.  Don't write the recursion exit clause properly, and it runs away.  Write it recursively, and 999 times out of a thousand it works -- then you find that 1 out of a thousand condition, like a subdirectory linked to a higher subdirectory in the tree somewhere, and it breaks down.

The truth is for each recursive call you ARE taking up some space on the stack, and you only have so much space on that stack. An iterative solution can take up less resources.

This is not a show-stopper by any means -- for many solutions, recursion is appropriate.  It just shouldn't be a 'magic bullet'.
AllanL5
Tuesday, January 24, 2006
 
 
Recursion isn't a bad word.  It just can go wrong really badly. 

A case I hit at work with a third party library.  They had a recursive quick sort.  We passed in some ungodly large data which was pretty much in order and our program crashed.  It ran out of stack space.  A previous version of the library didn't do this. 

One solution we tried was to up the stack space.  It worked but didn't solve all the headaches.  An even larger dataset would eventually cause this to fail as well.

The solution we put in was to pre-randomise the dataset so that the recursive quick-sort of the third party wouldn't recurse too much. 

Eventually the third party fixed the problem and we removed the randomization but it just goes to show that some care needs to be taken.
zekaric Send private email
Tuesday, January 24, 2006
 
 
Joel mentioned recursion as something that a computer programmer must know but from the follow up posts to that article, it seems like it's more important that you understand how to break tasks down into distinct blocks (and why) as opposed to actually using recursion in your programs.

I tend to agree with most of the people here on this forum; it's a very useful tool in very specific situations but it's not a cure-all.
TheDavid
Tuesday, January 24, 2006
 
 
Like a lot of other things, use recursion if you know what your usage circumstance is. In many cases, recursive code tends to be small, elegant and does its job well. If, for e.g., you know that the recursive depth isn't very large for your environment, then there's no harm in using it.
webdes
Tuesday, January 24, 2006
 
 
clcr, Mark, re: only "elegant" to academics

the inelegance is simply in the messiness of the fact that it calls itself, and anybody that is going to call it is drawn into the same vortex. In addition, often you want the top level call to specify an additional argument so you have to create two functions (a top level one and the recursive one) where one would have been more elegant.

Also, the inaccessibility of the stack can be a drawback in recursion compared to say in an iterative binary tree function where you use an stack array to provide essentially what the recursion would have provided but with visibility into the depth (array size) and flexibility to use that information.

Hard to explain, but if you have done enough recursion/iterative alternatives as I have you probably get the gist of what I am saying.
Anon and anon
Tuesday, January 24, 2006
 
 
"Hard to explain, but if you have done enough recursion/iterative alternatives as I have you probably get the gist of what I am saying."

I have done plenty of that, and I don't get the gist of what you're saying. I've replaced recursive algorithms with iterative ones on a number of occasions, and the iterative solution was only clearer in cases where the problem was not naturally recursive.
clcr
Tuesday, January 24, 2006
 
 
clcr, too bad, but thanks for responding. I guess my position is that even though tree traversal often lends itself to recursion, I still recommended the additional code needed to avoid recursion because of top level and stack visibility issues, not to mention exit simplicity. Those issues trounce any "elegance" of the function calling itself, in my opinion.
Anon and anon
Tuesday, January 24, 2006
 
 
"The solution we put in was to pre-randomise the dataset so that the recursive quick-sort of the third party wouldn't recurse too much."

Ouch.

For future reference, a better way to optimize a qsort is to randomize the pivot-points, rather than shuffling the initial dataset. Also, for each sub-partition, if the pivot point stays in the same place before/after the partitioning operation, it's often beneficial to iterate through the elements in that partition to check for already-sortedness.

More info here:

http://en.wikipedia.org/wiki/Quicksort
BenjiSmith Send private email
Tuesday, January 24, 2006
 
 
Oops. I just noticed that you said "third party". Not much you can do, in that case, other than randomize your input (as you did) and bitch about the fact that they didn't know how to properly protect a qsort implementation againts degenerate cases.
BenjiSmith Send private email
Tuesday, January 24, 2006
 
 
The programming approach one takes should be decided by the nature of the problem and the target system for which the code is to be executed on. Also some programming languages such as Lisp naturally use recursion.
Matthew Broten Send private email
Tuesday, January 24, 2006
 
 
Anon, I suppose it depends on the type of tree. One can safely traverse very large balanced trees recursively in a modest amount of stack space. For instance, a balanced binary tree 20 nodes deep can store over a million nodes.

On the other hand, I've learned the hard way not to operate on parse trees recursively unless I can guarantee that the input is trivial. Likewise, recursive descent parsers are not usually a good idea in the real world.
clcr
Tuesday, January 24, 2006
 
 
Okay, seems I need to give a lesson: (he says from the safety of his anonymity)

Making an iterative solution where a recursive one was easier can be a little extra work. But "less work" up front does not equal "elegant". In fact recursion is like a "goto", it is the "I need to be there" mentality without a structural programming understanding.

1. stack visibility: when a function calls itself, it cannot see the value of the variables one level up, whereas if you use an array of structs like a stack, you can see all levels at once and perform additional unforseen operations. Also with recursion you do not know the depth unless you keep an additional variable.

2. top level issue, recursion often leads you to use two functions where one would have done fine in a nicely contained iterative solution because of additional settings passed to the top level that are not important to the called levels.

3. complex exit requirements and backing out can cause recursion to be messy.

4. maintenance: adding an afterthought to a recursive function can be very messy. Recursive functions are rigid; they resist easy enhancement.

Conclusion: using recursion is usually the easy way out, and bad code design.
Anon and anon
Tuesday, January 24, 2006
 
 
correction to 2: The reason recursion often needs two functions is for the top level to do set up not required for sub-levels (this is especially common in a public functions).

clcr, everyone dwells on the issue of running out of stack space which is a valid point when you can't guarantee a relatively shallow max depth, but I think my other 4 points speak to the elegance.
Anon and anon
Tuesday, January 24, 2006
 
 
So having your code depending on values some arbitrary number of levels up the stack is exemplary design?  That seems a bit of a stretch to me.
anon Send private email
Tuesday, January 24, 2006
 
 
Discussing little algorithms that much? :-)

Recursion in modern programming is like finding a needle in a haystack. Sometimes they are useful, and depending on the programming language and on the program (task), they might be even more useful.

I for one use it to create main menus from data structures with callbacks. :-)

That said, I have learned to appreciate a little of functional programming, but the more that a program looks like functional programming, the more that I know that people will have a hard time trying to understand it. But for me, it's worth it because the code is reduced to "every line is meaningful", rather than the hundreds of lines of redundant code (if not coupled with XML) to get the same done. The drawback is that when using abstractions (indirections), people get lost more easily.
Lost in the jungle
Tuesday, January 24, 2006
 
 
anon, "depending on values some arbitrary number of levels up the stack" is just baiting, "depending" versus "having access" are two sides of the coin, not to mention the subtle shift from "elegant" to "exemplary".

I agree that "exemplary" design would tend on the surface toward removing access to that which is not relevant, however if there is any place it might be relevant it would be within the same function!

And you cannot discount my 4 points with an arguable objection to one of them.
Anon and anon
Tuesday, January 24, 2006
 
 
Lost, silly argument isn't it? But I do hold that recursion is never good, except for quick and dirty stuff.
Anon and anon
Tuesday, January 24, 2006
 
 
Anon, maybe. But I would rather program without limits than with limits (even if known).

If you are into programming with arbitrary limits, more power to you. I think recursion allows one to program without limits, but that is even more true depending on the programming language.

I avoid stuff like:

MAX_STACK = 1000
MAX_ITERATION = 1000000
MAX_sucks
Lost in the jungle
Tuesday, January 24, 2006
 
 
I often tend to use an explicit stack impl. instead of "pure" recusion. This way you don't blow the call-stack (you store only what you need).
Charlie
Wednesday, January 25, 2006
 
 
Lost.. said:"I for one use it to create main menus from data structures with callbacks. :-)"

Huh ?!! A callback function that is called recursively ?

Run, run, run, hell is near!!
It can't be... but I could be wrong Send private email
Wednesday, January 25, 2006
 
 
Oh no, things like:

menu = [
 '_File', [
    "_Quit", proc { quit },
    ],
 '_Help', [
    "_About...", show_about_proc,
    ],
]

mb = w.main_menu(menu)

The "procs" are the callback functions.

It's really neat in the way that the same code works for 3 different GUI backends, and it reminds me of the way C++ code was like when I read Charles Petzold's Win95 book.
Lost in the jungle
Wednesday, January 25, 2006
 
 
Recursion is a tool like any other. In some instances it's the natural way to deal with a problem (Fibonacci) and, in other cases, it's not (iterating over a list). In many cases, it's just personal preference and background.

As for blowing out your stack space, there are cases where that doesn't come into play:
* You know your input domain will never cause an issue, or
* The language/algorimth you're using works with tail recursion

It's my undestanding that gcc can even do tail recursion with C code nowadays.
Booch
Wednesday, January 25, 2006
 
 
I think if you are setting up your own stack then you are doing recursion-- just maybe not using the compiler/hardware's idea of recursion. It does make sense often (for large data structures or in that common case where there is also information shared between the invocations that, for one reason or another, you don't want to pass around-- even a pointer to it costs *some* stack), but your algorithm can still be recursive, even if your implementation  does not use the recursion feature of a particular language.

It would be nice to draw a correlation between the "Big O" (running time order) of an algoirthm & whether it is 'truly' recursive or iterative, but since logarithmic, linear and quadratic orders (and the rest) could all be exhibited by particular recursive algorithms, I'm not sure I can.
Simon Trew
Wednesday, January 25, 2006
 
 
I like recursion and have used it in production code with no problems. It does depend on your specific situation, however. I would not recommend implementing a recursive algorithm in an embedded system because of stack-space concerns. On a worstation, though? Recurse away!
even more anon for this....
Wednesday, January 25, 2006
 
 
"It would be nice to draw a correlation between the "Big O" (running time order) of an algoirthm & whether it is 'truly' recursive or iterative..."

Recursion is an implementation. Whether you use a recursive or an iterative implementation, the time complexity of the algorithm does not change. Actual execution time may, however.
A. Nonymous
Wednesday, January 25, 2006
 
 
I've seen XML parsers that recurse. You can guess what happens when the document is too deep. Oh dear...
Richard Rodger Send private email
Thursday, January 26, 2006
 
 
How do you keep your data in an iterative design? You put it in objects on the heap. No matter how you put it, you have just invented the stack as an abstract data type. This should be a bad thing, because you are reinventing the wheel. However, often your heap is larger than the available stack space.

If that is the case, that is a clear indication of another problem: wrong programming language for this recursive idiom. There are plenty of languages that do not have this limitation: some of them put the activation records on the heap (some implementations of Lips and Small-talk) or they allow tail recursion. Ideally, you have both.

Many posters made valid remarks about the limitations of recursion, but they forgot to mention that this is not a limitation of recursion per se, but of the tool they use.
Karel Thönissen Send private email
Thursday, January 26, 2006
 
 
Nobody said it so I will:
Any recursion can be traded into a loop and a stack.
This can even be proven but also makes sense: It is just how the function calls actually work.
U Send private email
Thursday, January 26, 2006
 
 
U:  That's right and also vice versa.  Church-Turing thesis and all that jazz.  Sometimes it's best to let the language system manage the stack state and sometimes not.
V Send private email
Thursday, January 26, 2006
 
 
RE: U. I said that ;)

RE: even more anon for this...
> "I would not recommend implementing a recursive algorithm in an embedded system because of stack-space concerns. On a worstation, though? Recurse away!"
Counter example: Writing a recursive directory/file scanner in Python (2.3?) on a workstation => blam! An impl. using explicit stack and loop => no prob.. (No artificially deep directories or similar either)
Charlie
Friday, January 27, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz