Algorithms can often be implemented recursively or nonrecursively; the decision rests with the programmer, who might shy away from a recursive solution because the algorithm might not terminate or that performance might be poor. In reality, recursion can allow for very elegant code as well as facilitating an interesting and economical type of code reuse. Software consultant Stephen B. Morris explores this interesting topic with a data-centric application drawn from the field of networking.
Thinking Recursively with C++
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSNews.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
Recursivity is a very good technique ton build algorithm. I enables you to think “easily”.
But a most impressive technique, once you have a well working recursive algorithm, is to know how to “un-recursive” it, this way you unleached the real power of the algorithm.
Recursivity is an old subject discussed in University for years, every programmers already know the advantages and drawbacks of recursivity, I did not find anything new in this article.
Edited 2006-03-27 01:29
“Recursive solutions are sometimes rejected based on unfounded fears concerning infinite loops or poor performance. In reality, recursive solutions can be highly elegant, easy to implement, and easy to maintain.”
Although I agree that ‘recursive solutions can be highly elegant, easy to implement, and easy to maintain”, I felt those three points fail to adress the proposed ‘fears concerning infinite loops or poor performance’
I also felt the article would have been better off showing any advantages or disadvantegs given both a recursive and itterative method.
Any recursive algorthm must include end conditions to mark the point in which the recursion gets unrolled. If you can define all the cases that mark the end, then you shouldn’t be solving the problem with recursion.
Poor peformance can be solved using caching techniques. For example, http://en.wikipedia.org/wiki/Memoization.
Well, memoization is a really neat (though kindof obvious) thing to have, but to be fair it really just replaces space-efficiency with time-efficiency…
true, but then again everything is a trade off of b/w time and space
For years after college, I searched for an opportunity to use a recursive algorithm to solve a practical problem. But every time I thought I found one, I realized I could code it simpler with just a loop.
Yeah, one can even use std::list or std::stack, or even hand-made stack for keeping temporary data, because there’s no need to return from hundreds of nested functions.
Recursions are very effective once you have some iteration in non linear graph like structures, (Trees are the perfect example)
Loops are easier for handling linear and multidimensional iterations.
In languages that do not have iterative-loop constructs, tail recursion is almost always optimized so that it doesn’t use stack space. This is a good thing, and thus most programmers who use these languages will try to use tail recursion whenever possible.
But sometimes, using non-tail recursion is unavoidable — and if you can only write a program in Scheme using recursion, then chances are it’s insanely complicated to write it iteratively.
What you’re really touching on is that recursive is a more general and more powerful technique than iteration. In fact, iteration basically boils down to tail recursion.
If you use iteration because your compiler won’t optimize tail recursion, then you’re doing the compiler’s work for it. I thought the point of high-level languages was so the compiler can do work for you?
I find it easier to think about recursive functions instead of iteration. I’ve been implementing tail recursion in C for a while which I find very efficient. No entry is pushed into the stack at every recursion and there is no need to return all the way back to the initial caller. Of course afterwards its very easy to rewrite them to their iterative form.
Btw.: I registered to OSNews in 1998 (When I got interested in writing kernels) but today I had to re-register while using the same username :|. Did it expire? Oh, and where did the forum go to?
Edited 2006-03-27 08:38
If you are unclear as to my opinions on recursion, please re-read my post.
Thankyou. 😉
For a lowlevel language that C++ wants to be, I find it amazing that it does not specify a way to manage control of execution flow. Recursion is good, sometimes it is the natural way of doing an algorithm, but C++ should have a way to encode tail call optimization without using hacks.
Lots of compilers automatically do tail recursion optimizations, including gcc.
Though some compilers won’t inline recursive calls after performing tail call optimization when they would inline an identical (after transformation) explicitly iterative solution. This isn’t because of a lack of any explicit annotation, I’m just bringing it up for informational purposes.
It is not part of the C++ standard though, so it can not be used to write portable code.
The link doesn’t work for me. Blank page.