Re: filling area by color atack safety

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.