Francois Grieu said:
[snip]
I note that the archetypal learning use case for recursion are
factorials and the "Tower of Hanoi", although both happen to have
a non-recursive solution which is much simpler:
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution
This should be a giveaway that recursion is seldom useful, since
instructors fail to find a good use case for it.
I think the reasoning here is bad. These examples are chosen
because they usually are already familiar to students outside the
realm of computing. More specifically, they are chosen to *explain*
recursion, not to *motivate* recursion. I think they do a good job
in this respect -- in both cases the recursive solutions are simple
enough and easy to understand. Calling the referenced non-recursive
tower-of-hanoi algorithm simpler, let alone much simpler, is highly
misleading; the *steps* may be simpler, but seeing how and why the
algorithm works certainly is not. Conversely, for a recursive
version it's easy to see at a glance both how it works and why, and
that's the point of the exercise - to present a simple example where
recursion can be understood. Deeper understanding, about when it
might be good to use recursion, and when not, comes only later.
I do acknowledge that
- the most natural solution to Tower of Hanoi is recursive,
simple and correct.
- Tower of Hanoi is thus a good introductory problem for
recursion in a computer class.
Okay, that's all good.
I stand by my points, as clarified below:
- Tower of Hanoi is *not* a good use case for recursion,
unless when learning/teaching is the purpose.
I think that depends on what one is trying to optimize. It's
probably faster to write a recursive version that is clearly
correct, and if time-to-market is a key concern then a recursive
solution is probably the right choice here (assuming of course
that ToH is a necessary part of whatever software is being
delivered).
I've re-thought my position. I'm now ready to admit that
recursion could be just the best way to code Tower of Hanoi,
when the problem is expressed in the (usual) way: start and
end state are all discs in a single tower; and/or the model of
the puzzle has no built-in way to tell the top disc.
On the other hand, the simple algorithm
move the smaller disk one step, circularly;
stop if the final position is reached;
make the single possible not involving the smaller disk;
repeat
is the easiest for a human, and to code when the starting point
is arbitrary and/or "top disc" is easy, e.g. the discs on each
peg are in three stacks, in the CS sense.
I'll just flat out disagree here. Recursion is often useful in
practice, and even when non-recursive solutions exist there
frequently are recursive solutions that are easier to understand,
or result in faster code, or both.
I think it depends what "practice" is. I admit I'm biased by
years of embedded systems programming with subtle problems when
re-entrancy happens, and/or libraries (e.g. for division) that
have been made reentrant (to be usable in an interrupt) at great
cost in efficiency; and/or CPUs with a physical stack limited
to 256 bytes. My company's cash cow today, used by million peoples
daily (a smart card), is in this category.
That's a bogus conclusion. Tower of Hanoi and other simple
example problems are used to illustrate recursion because the
problems are already familiar to students, not because of any
shortage of examples where a recursive solution is viable.
Sorting. Rendering of fractals. Compilers. Can't remembers I
met others in my professional life. I have sometime (not always,
far from that) implemented or met these without recursion in the
sense of a function calling itself as part of its own execution;
and on one occasion (Mergesort using actual casette tapes) the
stack was reduced to a single variable.
Certainly mergesort can be written iteratively using O(1) storage.
The idea that this can be done "simply and elegantly" is (a)
nebulously vague, (b) completely subjective, (c) an unsupported
opinion, (d) at best debatable, or (e) several of the above.
That's not consistent with the timing results pete reported.
Do you have any kind of supporting evidence to offer?
No.
I might loose that argument...
If you offer up both a program and an informal correctness proof
I might agree, but as an unsupported statement I don't buy it.
I have programmed myself both a recursive mergesort and an
iterative mergesort, and understood both well, and the iterative
version was definitely harder to get right than the recursive
version.
Agreed :-(
If you want to convince people otherwise you should
be prepared to provide a counterexample.
I'll eventually post sample code. But I get a deadline
approaching dangerously.
In my view this conclusion rests on some faulty premises,
as explained above.
I still think The Fastest Possible Mergesort (TM) does not
use recursion in the sense of a function calling itself.
What you're saying is that quicksort is good mostly for teaching
some of the *problems* associated with recursion, and one way of
getting around such problems.
I never said or thought that. Quicksort is a fast, very useful
sorting algorithm when coded carefully.
Forgive my cynicism, but this sounds
like you're subtly promoting an anti-recursion bias in the students.
I am (except for subtly).
Of course, I agree that it's important to understand the problem of
overly deep recursion, but this can be illustrated more easily with
a recursive function for measuring the length of a list, which in
turn can be used to show how to turn a non-tail-recursive function
into a function that is tail recursive (and thus easily iterizable
if one chooses to do that).
When I google "quicksort source" the first hit is
http://cprogramminglanguage.net/quicksort-algorithm-c-source-code.aspx
which falls into the category that may overflow a 1MB stack
when sorting 50k elements, if they are deliberately ordered for
that purpose. I'm afraid many practicing programmers are unaware of
that, and thus IMHO should not use recursion in the real world,
where deliberate denial of service is a reality.
As a counterpoint, the paper "Engineering a Sort Function", one of
the most widely cited papers about how to do a good job implementing
qsort, embraces recursion down *both* branches of sorting subarrays.
Quoting from the paper:
We have not adopted many customary improvements. By
managing a private stack we could cut stack space from
nearly 20 variables to 2 per level. By sorting the larger
side of the partition last and eliminating tail recursion,
we could reduce worst-case stack growth from linear in /n/
to logarithmic. Neither trick is worth the effort.
In the same paragraph they acknowledge that worst case input cause
"a quick memory fault" for precisely that linear stack usage. And
in several of their example code, that input is easy to construct.
Fortunately, some implementors know better than use that kind of
algorithm.
One widely distributed example is Microsoft's C standard library
(VC\crt\src\qsort.c); it does not use explict recursion; it precisely
controls stack depth. I've seen that in at least two other libraries
standard C libraries (one is under NDA, can't remember the other).
qsort in libc indeed tends to reference "Engineering a Sort Function"
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
and use recursive call, but often explicitly remove tail recursion
and use a non-trivial pivot selection strategy; I can't tell the
maximum stack usage.
Personally I'm more likely to be convinced by Jon Bentley and Doug
McIlroy than by the (presumed) statements of anonymous developers
working on some unknown C libraries.
Are you advocating that it would be tolerable that the C standard
library qsort() crash with stack overflow on medium-sized input?
Francois Grieu
