Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 18 Mar 2024 14:23:51 +0200
Organization: A noiseless patient Spider
Lines: 50
Message-ID: <20240318142351.00001849@yahoo.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>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: dont-email.me; posting-host="e438cc7fdcf3a4669168787da7dbc3da";
	logging-data="3825776"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18m4njrRe+3YiuWGKi+tkThYJVimxDbCKI="
Cancel-Lock: sha1:hoYLuR7Cinc/0of9eDpl29CALHk=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 3234

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.