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
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: <87wmq2jn7s.fsf@bsb.me.uk> <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 writes:
> On Mon, 18 Mar 2024 03:00:32 -0700
> Tim Rentsch wrote:
>
>> bart writes:
>>
>>> On 16/03/2024 13:55, Ben Bacarisse wrote:
>>>
>>>> Malcolm McLean 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.