Path: ...!weretis.net!feeder6.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: fir <fir@grunge.pl>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Tue, 19 Mar 2024 16:05:50 +0100
Organization: i2pn2 (i2pn.org)
Message-ID: <utc9kb$2d06e$1@i2pn2.org>
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=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 19 Mar 2024 15:05:48 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2523342"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="+ydHcGjgSeBt3Wz3WTfKefUptpAWaXduqfw5xdfsuS0";
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:27.0) Gecko/20100101 Firefox/27.0 SeaMonkey/2.24
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <20240318142351.00001849@yahoo.com>
Bytes: 4305
Lines: 77

Michael S wrote:
> 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.
>
in reality it is less i guess..
well that would be like if i would like to recolor
vertical line of say length 2 milion pixels
- i would go always one pixel right 2 milion times

if this is 100x 100 square and i put the initioation
in middle it would go 50x right then at depth 50
it would go one up than i guess 100 times left

then just about this line up until up edge of picture
- then it probably revert back (with a lot
of false is) to first line and then go down

- so it seems (though i was not checkingh it
tu much in my head) that the depth in that case
would be about half

- but this is becouse its much unfortunate,
'normally' i think the recursion depth
should be more like to edge of an area

(i will answer more later as i hate usenet by newsreader
so unconveniant to read and answer its pain)

the problem has a couple of aspects imo
- interesting is in fact the great simplicity
of this recursion method esp in that case - which gives to think