is recursion necessary? (was Re: Should I convert FORTRAN code to C?)

[T. William Wells]

In article <WAYNE.88Jul9134227 at dsndata.uucp>, wayne at dsndata.uucp (Wayne Schlitt) writes:
> I used to think that recursion was unnecssary and very expensive, but
> now i am not so sure.  what about the cases where you recurse from
> more than one place?  can you do that without a stack of flags and
> lots of ifs?  an example, how would you do something like this:
>
> [example omitted]

I'll be very surprised if your message does not draw flames from
both the recursion and anit-recursion fanatics. But let me
inject some common sense into what is likely to become a
religious debate.

The question you posed is meaningless.  `Necessary' has a meaning
only in a definite context.  Since programming is a utilitarian
art, like architecture, the appropriate question is "Is
recursion the right tool for job X?" If the answer to that is
indefinite, one can then ask: "Is recursion the most esthetic
tool for job X?"

So, to give some examples: should one code strlen() using
recursion? (This from an idiot debate I got sucked into on
comp.misc). Obviously no.

Should one use recursion when the processor your program is to
run won't be able to handle the stack? (Consider the poor soul
limited to 256 bytes in a 6502 stack.) Or, when you need to
control memory use and have no good way to check the amount of
memory used by the stack? Obviously no.

Should one use pure tail recursion? Depends on the programming
language. In C, one should not use tail recursion; the only
compiler that I know of that will optimize this out is gcc.
Arguing that that is sufficient reason is very parochial. In
Scheme, on the other hand, tail recursion is absolutely the way
to go.

Should one use recursion when the stack depth and function call
overhead are not issues and there is a reasonable nonrecursive
method of implementation? That is an esthetic issue.

How about when the nonrecursive implementation is just the
recursive implementation in disguise? Obviously yes.

The point of all this is that recursion is just a tool. It is
not a magic bullet as its enthusiasts claim, nor is it a ticket
to hell as its detractors claim. Like any other tool, it has to
be evaluated as to its appropriateness to the job.

You might note that my examples are weighted towards not using
recursion. There are several reasons for this, however, the main
one is that, at least in C, unlike other control structures,
recursion has an overhead that can't usually be avoided or
ignored.  In the real world, resources usually have limits that
we are going to have to be aware of and which will affect the
algorithms we choose.