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.