Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: bart Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety Date: Tue, 19 Mar 2024 17:16:42 +0000 Organization: A noiseless patient Spider Lines: 97 Message-ID: References: <87wmq2jn7s.fsf@bsb.me.uk> <86ttl3oo5b.fsf@linuxsc.com> <20240318142351.00001849@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 19 Mar 2024 17:16:38 -0000 (UTC) Injection-Info: dont-email.me; posting-host="476cbb70b59e552cddbf69eebbcfa758"; logging-data="1005145"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX190lu94TyiAIncpOsJnoIvB" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:MRfwMEbgGSt6nmEo4OSFqSqNJRg= In-Reply-To: Content-Language: en-GB Bytes: 5774 On 19/03/2024 15:05, fir wrote: > Michael S wrote: >> 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. >> > 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.