Re: Recursive functions

"Bill Pursell" <bill.pursell@xxxxxxxxx> writes:
On Apr 1, 9:10 pm, Lauri Alanko <l...@xxxxxx> wrote:
In article <1175456107.493063.221...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Bill Pursell <bill.purs...@xxxxxxxxx> wrote:
Because it is totally inappropriate to use a recursive
function to compute the length of a string.

"Totally inappropriate" apparently means here "inefficient on a
typical C implementation". That is certainly true, but not always
crucial. Even the space performance isn't an issue if the lengths of
all argument strings are known to have a reasonable bound.

Efficiency aside, recursion is certainly a natural way of defining the
length of a sequence.

It is a natural way of defining the length of a finite sequence
in a mathematical setting. It is not completely unnatural
to define the length of a finite sequence in terms of recursion
on a computer. However, it IS totally inappropriate to compute
the value using recursion. Totally inappropriate does
not mean "inefficient in a typical C implementation". It
is, rather, a euphimism for "completely boneheaded".

In real-world C code, I agree. <OT>In Lisp-like languages, it might
be perfectly appropriate.</OT>

But homework assignments are not real-world code; consider how easily
we can tell the difference when people post here asking for help. The
canonical first program is "Hello, world". That's not something for
which there's any real-world requirement. The existing "echo" command
on many systems is an easier and more flexible way to print an
arbitrary message. If I had an actual requirement to print the string
"Hello, world", writing a C program wouldn't be my first choice. But
the point of the program is to learn how to create, compile, and
execute a C program. Using a minimal example lets the beginner do
this without other considerations getting in the way.

Similarly, problems that actually require recursion tend to be more
complex than might be appropriate for a beginner, but we *can* teach
the elements of recursion using artificially simple example, like
computing the length of a string. It might be appropriate to mention
in passing that recursion really isn't the best solution (in fact, a
call to the strlen() function is) -- and for all we know, the OP's
instructor might have mentioned that.

Later on, I'd probably use something like Quicksort as an example of
something where recursion *is* appropriate -- and I might assign a
non-recursive Quicksort (using an explicit stack) to demonstrate that
it's possible, and to show that using the function call mechanism lets
the language take care of a lot of the details for you. I'd probably
also assign, or at least discuss, a recursive Fibonacci function to
demonstrate a case where simple recursion is a *really* bad solution.
But that can come later.

--
Keith Thompson (The_Other_Keith) kst-u@xxxxxxx <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
.

Relevant Pages

  • Re: Recursive functions
    ... function to compute the length of a string. ... It is a natural way of defining the length of a finite sequence ... to define the length of a finite sequence in terms of recursion ... it IS totally inappropriate to compute ...
    (comp.lang.c)
  • Re: Recursive functions
    ... function to compute the length of a string. ... It is a natural way of defining the length of a finite sequence ... it IS totally inappropriate to compute ... not mean "inefficient in a typical C implementation". ...
    (comp.lang.c)
  • Re: Recursive functions
    ... function to compute the length of a string. ... "Totally inappropriate" apparently means here "inefficient on a ... recursion is certainly a natural way of defining the ...
    (comp.lang.c)
  • Re: Article on Herbert Schildt, author of C Unleashed, repaired on wikipedia
    ... that deliberately went one beyond the end of the string, ... Within its framework, which sucks, it is a correct program. ... To do this you changed a value parameter to a reference parameter and ... this makes the recursion go wrong. ...
    (comp.programming)
  • Re: Three Kinds of Logical Trees
    ... > I think this is just a representation issue. ... > I do have a number, but I am only ttreating as a string. ... I was attempting to isolate the question of tree structure; ... it's not much of an issue; no one uses recursion much. ...
    (comp.databases.theory)