Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 18 Mar 2024 14:13:19 -0700
Organization: A noiseless patient Spider
Lines: 59
Message-ID: <86cyrrnt00.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <ut4020$2s8ov$1@dont-email.me> <87wmq2jn7s.fsf@bsb.me.uk> <ut4b3c$2ugk7$1@dont-email.me> <86ttl3oo5b.fsf@linuxsc.com> <20240318142351.00001849@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="392b353a6389bc0498ba35815d55dc9d";
	logging-data="411090"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19teQHh7SrcdomRKy3bQSK4/EqupxnqyME="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:Pd92Ogl8b0MmzpOLXCPranPZLu0=
	sha1:colpZNfYvFXxTZ7w739drJC+SLU=
Bytes: 3698

Michael S <already5chosen@yahoo.com> writes:

> On Mon, 18 Mar 2024 03:00:32 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> bart <bc@freeuk.com> writes:
>>
>>> On 16/03/2024 13:55, Ben Bacarisse wrote:
>>>
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> Recursion make programs harder to reason about and prove correct.
>>>>
>>>> Are you prepared to offer any evidence to support this astonishing
>>>> statement or can we just assume it's another Malcolmism?
>>>
>>> You have evidence to suggest that the opposite is true?
>>
>> The claim is that recursion always makes programs harder to reason
>> about and prove correct.  It's easy to find examples that show
>> recursion does not always makes programs harder to reason about and
>> prove correct.
>>
>>> I personally find recursion hard work and errors much harder to
>>> debug.
>>
>> Most likely that's because you haven't had the relevant background
>> in learning how to program in a functional style.  That matches my
>> own experience:  it was only after learning how to write programs in
>> a functional style that I really started to appreciate the benefits
>> of using recursion, and to understand how to write and reason about
>> recursive programs.
>>
>>> It is also becomes much more important to show that will not cause
>>> stack overflow.
>>
>> In most cases it's enough to show that the stack depth never exceeds
>> log N for an input of size N.  I use recursion quite routinely
>> without there being any significant danger of stack overflow.  It's
>> a matter of learning which patterns are safe and which patterns are
>> potentially dangerous, and avoiding the dangerous patterns (unless
>> certain guarantees can be made to make them safe again).
>
> The problem in this case is that max. depth of recursion is O(N)
> where N is total number of pixels to change color.  So far I
> didn't find an obvious way to cut the worst case by more than
> small factor without turning recursive algorithm into something
> that is unrecognizably different from original and require proof
> of correction of its own.  Classic 'divide and conquer smaller
> part first" strategy does not appear applicable here, or at least
> not obviously.

Right.  I said as much in another reply to you.  This problem
is not well suited to a recursive solution.

To clarify my earlier comment, when I say I routinely use
recursion I do not mean I always use recursion.  Part of
understanding programming in a functional style is knowing
when not to use recursion as well as when to use it.