«

On 24/11/2010 09:26, Tim Rentsch wrote:
> Francois Grieu<> writes:
>
>> On 23/11/2010 01:09, Tim Rentsch wrote:
>>> Francois Grieu<> writes:
>>>
>>>> [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_o...rsive_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.

>> - Recursion is seldom useful in practice, where non-recursive
>> solutions often exist and lead to simpler code.
>
> 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.

>> - There are so few counterexamples to the above that recursion
>> is taught with problems like Tower of Hanoi that are both
>> artificial and with a shorter and more efficient
>> non-recursive algorithm.
>
> 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.

>> Similarly, Mergesort, which someone in this thread sees as a
>> good use case of recursion, is indeed a good problem for
>> teaching recursion.
>
> Okay.
>
>> It can also be written simply and elegantly
>> with a single size_t variable rather than reentrant call or
>> stack array;
>
> 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.
>
>> once this is grasped, the code gets shorter and
>> more efficient,
>
> That's not consistent with the timing results pete reported.
> Do you have any kind of supporting evidence to offer?

No.

>> and arguably as easy to derive.

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 Mergesort is thus not a good use case for recursion
>> in the sense that implies a reentrant function.
>
> 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.


>> Quicksort is an excellent problem for teaching on recursion,
>> because
>> - Applying to a simple Quicksort just what was learned from
>> recursion in Tower of Hanoi leads to code that superficially
>> works, but on many architectures will overflow the execution
>> stack for specially constructed input. Such failures are part
>> of the process of learning.
>> - There is a portable way out of that (using recursion for
>> the smallest problem only, solving that one first, and
>> replacing tail recursion for the rest by iteration).
>
> 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/quic...urce-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.

>> Several qsort() C library source that I looked at do not use
>> recursion in the sense that implies a reentrant function.
>> In fact, having no reentrant function is a design objective
>> of some C libraries, for portability, testability, and
>> efficiency reasons.
>
> 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/sour...d/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

On Nov 22, 8:43*pm, j...@toerring.de (Jens Thoms Toerring) wrote:
> Super Ted <nos...@nospam.com> wrote:

<snip>

> > * if(strlen(t) == 0)
> > * * * * * return; // handle null strings
>
> That's an empty string. And then a simple
>
> * * *if ( ! *t )
> * * * * *return;
>
> is more efficient.

by how much and on what platforms? Do you have figures?
It's also significantly less clear.

<snip>

On Nov 28, 11:09*am, Nick Keighley <nick_keighley_nos...@hotmail.com>
wrote:
> On Nov 22, 8:43*pm, j...@toerring.de (Jens Thoms Toerring) wrote:
>
> > Super Ted <nos...@nospam.com> wrote:
>
> <snip>
>
> > > * if(strlen(t) == 0)
> > > * * * * * return; // handle null strings
>
> > That's an empty string. And then a simple
>
> > * * *if ( ! *t )
> > * * * * *return;
>
> > is more efficient.
>
> by how much and on what platforms? Do you have figures?
> It's also significantly less clear.
>
> <snip>

oops! If I'm going to be sarky I should also be correct. Yes calling
strlen to test for an empty string is daft. But I'd prefer an explicit
test

if (t[0] == 0)

or

if (*t == '\0')

On Nov 23, 11:36*am, Francois Grieu <fgr...@gmail.com> wrote:
> On 23/11/2010 05:28, pete wrote:
>
> > To change my recursive 8 queens program into a 20 queens
> > program, all I have to do is change this line:
> > #define SQUARES 8
> > to
> > #define SQUARES 20
> > I think it would be a lot more work than that,
> > to change an iterative version.
>
> Depends on the iterative code you are starting from.

yes I'm pretty sure the solution I wrote long ago would have been
easily extendable.It certainly didn't have 8 nested loops as the most
naive iterative solution might

> A short, readable, conformant C program can count solutions
> to the SQUARES queens problem (or show one), with the above
> property, and no function recursively called.
> I'm not considering using the macro processor to produce
> nested loops, but using an array to implement a stack
> SQUARES deep.
>

Francois Grieu <> writes:

> On 24/11/2010 09:26, Tim Rentsch wrote:
>> Francois Grieu<> writes:
>>
>>> On 23/11/2010 01:09, Tim Rentsch wrote:
>>>> Francois Grieu<> writes:
>>>>
>>>>> [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_o...rsive_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.

The steps might be easier, whether/why it works isn't.

>>> - Recursion is seldom useful in practice, where non-recursive
>>> solutions often exist and lead to simpler code.
>>
>> 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. [snip]

I mean "Application to some real-world programming problem."

>>> - There are so few counterexamples to the above that recursion
>>> is taught with problems like Tower of Hanoi that are both
>>> artificial and with a shorter and more efficient
>>> non-recursive algorithm.
>>
>> 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. [snip]

Probably largely self-selection. If one isn't accustomed to
looking for recursive solutions, one tends not to see them,
and vice versa.

>>> Similarly, Mergesort, which someone in this thread sees as a
>>> good use case of recursion, is indeed a good problem for
>>> teaching recursion.
>>
>> Okay.
>>
>>> It can also be written simply and elegantly
>>> with a single size_t variable rather than reentrant call or
>>> stack array;
>>
>> 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.
>>
>>> once this is grasped, the code gets shorter and
>>> more efficient,
>>
>> That's not consistent with the timing results pete reported.
>> Do you have any kind of supporting evidence to offer?
>
> No.
>
>>> and arguably as easy to derive.
>
> 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 Mergesort is thus not a good use case for recursion
>>> in the sense that implies a reentrant function.
>>
>> 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.

I expect there are regimes where recursive mergesort is faster,
and also regimes were iterative mergesort is faster. But even
when non-recursive mergesort has better performance, a recursive
version might be preferable for other reasons such as code clarity.

>>> Quicksort is an excellent problem for teaching on recursion,
>>> because
>>> - Applying to a simple Quicksort just what was learned from
>>> recursion in Tower of Hanoi leads to code that superficially
>>> works, but on many architectures will overflow the execution
>>> stack for specially constructed input. Such failures are part
>>> of the process of learning.
>>> - There is a portable way out of that (using recursion for
>>> the smallest problem only, solving that one first, and
>>> replacing tail recursion for the rest by iteration).
>>
>> 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.

I'll amend my statement: what you're saying is that, in the context
of education about recursion, quicksort is good mostly for teaching
some of the *problems* associated with recursion, etc.

>> 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/quic...urce-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.

Lots of people write recursive code badly. So what? Lots of people
write for-loops, or pointer manipulation, or sorting routines, or
almost any other kind of coding idiom, badly. That doesn't mean
those things ought to be avoided.

>>> Several qsort() C library source that I looked at do not use
>>> recursion in the sense that implies a reentrant function.
>>> In fact, having no reentrant function is a design objective
>>> of some C libraries, for portability, testability, and
>>> efficiency reasons.
>>
>> 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.
> [snip]

Irrelevant if the bad inputs occur with a probability less than that
of the Sun going nova tomorrow.

> 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/sour...d/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?

I'm not advocating anything about qsort. I'm saying the example
of Bentley and McIlroy, who describe both what they are trying
to achieve and the engineering principles and reasoning behind
their decisions, has more much value and power to convince than
any restatement of a conclusion reached by unknown persons working
under unknown constraints using unknown principles and unknown
reasoning. In short I think it's better for the students if they
learn how to think, rather than just what conclusions to recite
on their exams.

Keith Thompson <kst-> writes:

> Tim Rentsch <> writes:
>> writes:
>>> Ian Collins <ian-> wrote:
>>>> Yes, it took a while for the penny to drop for me as well. Maybe
>>>>
>>>> "Provided that a library function can be declared without reference to
>>>> any type defined in the standard header where the function is declared"
>>>>
>>>> Would be better wording.
>>>
>>> I think it should be more like "...defined only in the standard
>>> header...". If the type is also defined in a different header, then
>>> including that header should suffice. In short, I'm pretty sure the
>>> intent was that declaring a function by hand should work as long as you
>>> can do it "correctly". But it's hard to say "correctly" in standardese.
>>
>> I've read this opinion twice now, and it surprised me both times.
>> The plain reading is clear enough, and seems to make no effort in
>> the "correctly" direction. It seems just as likely, or perhaps
>> even more likely, that the intention was to allow declarations of
>> functions that existed before the Standard, but any function that
>> needed a "new" type (ie, a type defined in some system header)
>> must be declared by #include'ing the appropriate header. This
>> would allow old code to work K&R style, but new code must do the
>> right thing. Doesn't that seem like a more plausible explanation?
>
> Not to me.
>
> I think the point is that the function declarations provided by headers
> are just C function declarations. A declaration needs to be visible in
> order to call a library function, and it doesn't matter to the compiler
> whether that declaration comes from a #included header or is part of the
> source file being compiled.
>
> In what plausible way could this program:
>
> #include <stddef.h>
> int main(void)
> {
> size_t strlen(const char *s);
> return strlen("");
> }
>
> fail in a real implementation? [snip]

It could nicely and conformingly fail by having the compiler
issue a diagnostic message

ERROR: 'strlen()' called without a '#include <string.h>' directive.

and then refusing to compile the file. And I believe that allowing
this behavior from a conforming compiler has value.