By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,276 Members | 1,410 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,276 IT Pros & Developers. It's quick & easy.

Question: How do you feel about recursion?

P: n/a
Greetings.

I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.
Jul 19 '05 #1
Share this Question
Share on Google+
12 Replies


P: n/a
da Vinci <bl***@blank.com> wrote in message
news:um********************************@4ax.com...
Greetings.

I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.
Anything that does a good job is acceptable. Recursion is no exception. You
can't generalize about such things.
Should we readily use it when we can or only when absolutly forced to
use it?
Use it if it's the best solution in the circumstances (where "best" can mean
quickest or easiest to implement, easiest to understand, easiest to
maintain, fastest to execute, etc. etc., whatever matters to you the most).
I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


To do something like searching for a file on a system with a nested
directory structure, I would certainly do it with recursion because it's
quick and easy to write and very effective. For something like a factorial
calculation, which can be done recursively, a simple loop is probably much
more effective. It really depends on what problem you want to solve.

DW

Jul 19 '05 #2

P: n/a
da Vinci <bl***@blank.com> wrote in
news:um********************************@4ax.com:
Greetings.

I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


In some languages, recursion, especially tail recursion, is more natural
than in others. In Lisp, for example, I think you would use recursion to
implement what in other languages would be a simple loop.

In a language like C++ you would normally use recursion only when an
iterative solution would require implementing an explicit stack to store
the algorithmic state. Since a stack is required anyway, might as well
use the call stack if it simplifies the implementation. Traversing a tree
structure would be an example of something best implemented recursively.
The only caveat is the limited stack space some environments impose.

Computational algorithms that are expressed as recurrence relations, such
as Fibonocci sequence or factorial, are generally better implemented
iteratively, since such an implementation does not require a stack, and
so is simpler and faster done interatively.

Gregg
Jul 19 '05 #3

P: n/a
da Vinci wrote:
Greetings.

I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


When a recursive solution is natural for a given problem -- and you
know it is well bounded (i.e. will not get too deep) -- use it. If
it proves to be a bottleneck (as discovered through profiling) you
can always rewrite it as iteration. Some C++ compilers, in
optimizing mode, can even transform some tail recursive algorithms
into iteration by themselves.

In any event, *understand* recursion. You may not use it in your
actual code but it will quite likely inform your programming -- and
improve it.

That said, you're really off-topic here; please take your question
to news:comp.programming. [f'ups set]

HTH,
--ag
--
Artie Gold -- Austin, Texas
Oh, for the good old days of regular old SPAM.

Jul 19 '05 #4

P: n/a
da Vinci wrote:
...
I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


The term "recursion" has many different meanings, depending on the
context. There is no point to start a debate about "recursion" without
providing a clear definition for the term. What kind of recursion your
question is about? Syntactical recursion, when one function in C or C++
program calls itself directly or indirectly? Algorithmical recursion,
which implements stack-based version of 'divide & conquer' approach?
Something else?

--
Best regards,
Andrey Tarasevich
Brainbench C and C++ Programming MVP

Jul 19 '05 #5

P: n/a
Andrey Tarasevich writes:
da Vinci wrote:
...
I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


The term "recursion" has many different meanings, depending on the
context. There is no point to start a debate about "recursion" without
providing a clear definition for the term. What kind of recursion your
question is about? Syntactical recursion, when one function in C or C++
program calls itself directly or indirectly? Algorithmical recursion,
which implements stack-based version of 'divide & conquer' approach?
Something else?


Jeez.

Use recursion when it's natural. If its use strikes you as forced (as in
factorial), it probably is. I would not want to code a tree or fiddle with
the DOS file structure if I had a language that did not support recursion.
The original languages, Cobol, Fortran and Basic could not "do" recursion.
Your instructor might be from that era.
Jul 19 '05 #6

P: n/a

"da Vinci" <bl***@blank.com> wrote in message
news:um********************************@4ax.com...
Greetings.

I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


It's good for learning and making you think of new techniques. It does make
certain problems much simpler, but in fact in general programming it's not
often used. (I didn't say never.)
Jul 19 '05 #7

P: n/a
da Vinci wrote:
Greetings.

I want to get everyone's opinion on the use of recursion.

We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.

Should we readily use it when we can or only when absolutly forced to
use it?

I appreciate any responses. Just wanted to get a feel for it. I
received a pretty dirty opinion of it tonight in class.


You should recurse when you are doing something that naturally lends to
it (seaching a tree, the main example you will come across in normal
life is searching a hard disc).

The overheard that comes from recursion unless you are doing 10,000s of
levels is tiny, and almost certainly smaller than the improvement you
would get with algorithms improvements. Also there is a good chance your
attempts to avoid recursion will be less efficent than just doing it
(this applies more and more with modern compilers)
Jul 19 '05 #8

P: n/a
In article <um********************************@4ax.com>, bl***@blank.com
says...

[ ... ]
I want to get everyone's opinion on the use of recursion.
That's a bit like asking "I want people's opinions of large trucks."
It's so vague as to be nearly meaningless.
Should we readily use it when we can or only when absolutly forced to
use it?


IMO, you should readily use it when doing so will lead to code that's
easier to read and/or write than doing otherwise. Using it to create
simple loops is pointless except in languages (e.g. LISP) that don't
really support loops directly, or in situations (e.g. template meta-
programming) where the language does, but not under the circumstances
you care about.

OTOH, there are also times that recursion seems to be a natural fit, but
ends up working relatively poorly. Elsethread, traversing a tree-like
file system has been mentioned, so I'll use it as well. The problem
here is that traversing a tree-like file system recursively naturally
tends to lead to a depth-first traversal, but this tends to make
exceptionally poor use of caching. At least with all the OSes I've
programmed, if you care much about speed, you're almost always better
off doing a breadth-first traversal instead.

This way, you read an entire directory at once, and then go to the next
directory. This can avoid quite a bit of disk seeking as well as
improving cache usage. The difference depends a lot on the directory
structure, but if (for example) you were searching a large disk, a 10:1
speed improvement wouldn't be surprising at all.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 19 '05 #9

P: n/a
osmium wrote:
...
The term "recursion" has many different meanings, depending on the
context. There is no point to start a debate about "recursion" without
providing a clear definition for the term. What kind of recursion your
question is about? Syntactical recursion, when one function in C or C++
program calls itself directly or indirectly? Algorithmical recursion,
which implements stack-based version of 'divide & conquer' approach?
Something else?

...
Use recursion when it's natural. If its use strikes you as forced (as in
factorial), it probably is. I would not want to code a tree or fiddle with
the DOS file structure if I had a language that did not support recursion.
The original languages, Cobol, Fortran and Basic could not "do" recursion.
...


Once again, the correctness of these statements greatly depends on the
concrete meaning of the term "recursion" (and believe me, it has more
than one). This has been discussed to death in more appropriate places.
I don't see any reason to do it again here.

--
Best regards,
Andrey Tarasevich
Brainbench C and C++ Programming MVP

Jul 19 '05 #10

P: n/a
On Tue, 28 Oct 2003 10:02:52 -0800, Andrey Tarasevich
<an**************@hotmail.com> wrote:
Once again, the correctness of these statements greatly depends on the
concrete meaning of the term "recursion" (and believe me, it has more
than one). This has been discussed to death in more appropriate places.
I don't see any reason to do it again here.


Then lets not.

I just learned it last night and with everything, I wanted the "pros"
opinion on it. I wasn't aware there was more than one type as *I just
learned it*. I was refering mainly to the fact of a function calling
itself.

I have made a few posts in the past regarding different issues and
have been told by many people on the group that the way I was doing
something was not accepted in the real world. I want to learn what IS
acceptable.

As I said, quite a few things I have learned already are actually NOT
acceptable in the real world. So, I have curtailed my use of those
practices on the advisement of group members. (The big one being that
I was told that using the header call of #include <whatever.h> was
perfectly fine to use in C++ and group members advised me otherwise.)

So, this thread was begun with the intent to see if recursion is
generally accepted or if it is shunned.

I was unaware there are multiple meanings to recursion, other than
just a function calling itself.
Jul 19 '05 #11

P: n/a
da Vinci wrote:

Greetings.

I want to get everyone's opinion on the use of recursion.


It makes me feel good.
And THAT makes me feel good.
Which makes me feel good.
<recurse ad nauseum>

:)
Jul 19 '05 #12

P: n/a
In article <um********************************@4ax.com>,
da Vinci <bl***@blank.com> wrote:
Greetings.

I want to get everyone's opinion on the use of recursion.


The answers will probably be the same as if you asked everyone's
opinions on linked lists.

Recursion is a tool. It can be an obvious and good choice, an obvious and
bad choice (using it to compute the nth Fibonacci number is an example of
that), and one that is completely inapplicable to the problem.

If it isn't in your bag of tricks you will be the poorer for it. If you
use it everywhere it can be used then you will undoubtedly use it in places
where it shouldn't be used.

Alan
--
Defendit numerus
Jul 19 '05 #13

This discussion thread is closed

Replies have been disabled for this discussion.