Re: filling area by color atack safety

On 19/03/2024 15:05, fir wrote:

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

That's what I thought until I tried it.
If I start with an 18x18 image of all zeros, then fill starting from the centre with a 'colour' that is an incrementing value, then the final image displayed as a table of integers looks like this:
171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
  99  98  97  96  95  94  93  92  91  90  89  88  87  86  85  84  83  82
  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81
  63  62  61  60  59  58  57  56  55  54  53  52  51  50  49  48  47  46
  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45
  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10
172 173 174 175 176 177 178 179 180   1   2   3   4   5   6   7   8   9
209 210 211 212 213 214 215 216 181 182 183 184 185 186 187 188 189 190
208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235
253 254 255 325 257 258 259 260 261 262 263 264 265 266 267 268 269 270
288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307
By following the sequence starting from 1, you can see the fill-pattern.
It's not clear how it gets from 171 at top left to 172 half-way down the left edge.