Path: csiph.com!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!news.uzoreto.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Recursion v Memoization
Date: Mon, 11 Jan 2021 06:34:39 -0800
Organization: A noiseless patient Spider
Lines: 70
Message-ID: <86h7nnpmo0.fsf@linuxsc.com>
References: <rsg72i$eq4$1@gioia.aioe.org> <861rf6uzw4.fsf@linuxsc.com> <1b1rf2zsuf.fsf@pfeifferfamily.net> <86h7nwrq8s.fsf@linuxsc.com> <rt0pr4$k4g$1@dont-email.me> <86tursq55e.fsf@linuxsc.com> <rtgoir$jte$3@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="e003f7479dce81a6c34051fbd9d3e250"; logging-data="22875"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/2qrU048Vuu37icFM37frKDJmGSnxb+gg="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:xW96bg4hFBw7Bi/Z+K2lTZY3chQ= sha1:49HhwbyoTOJdWbF6mdfSm9nhWvw=
Xref: csiph.com comp.lang.c:158285

beej@beej.us (Beej) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> For floodfill usually it's better to use a breadth-first traversal.
>
> Interesting.  Elaborate?

Here are two versions of a flood fill algorithm.  They are the
same except one treats the array s as a stack, the other as a
queue.  Don't worry about the "infinite" array, that will be
addressed following.  Please excuse the mixture of C and
pseudo-code.

    fill( fill-point, other stuff ){
        let s be a local array, "infinitely" large
        Index a = 0, b = 0;
        color fill-point the new color
        s[ b++ ] = fill-point
        while a < b {
            Point p = s[ --b ];
            for each neighbor, n, of p that has the old color {
                color n the new color
                s[ b++ ] = n
            }
        }
    }

    fill( fill-point, other stuff ){
        let s be a local array, "infinitely" large
        Index a = 0, b = 0;
        color fill-point the new color
        s[ b++ ] = fill-point
        while a < b {
            Point p = s[ a++ ];
            for each neighbor, n, of p that has the old color {
                color n the new color
                s[ b++ ] = n
            }
        }
    }

The queue version expands breadth first.  The stack version
expands depth first, and hence corresponds to recursion.

Of course we cannot have an "infinite" array.  In most cases a
fairly small array will suffice (a somewhat more sophisticated
algorithm helps reduce the size, but it's not important to
understand the details of that).  If the array is finite rather
than "infinite" then naturally the queue version needs to use
modulo arithmetic to keep a and b in range, but I'm sure you
can work that out so I won't go into any more detail on that.

However, with the array being finite, we need to be prepared for
the possibility that the array will fill up.  One way to do that
is have the array be allocated dynamically, using malloc/realloc
to grow the array as needed.  Another way is for fill() to call
itself recursively when s is full, with a small fixed-size array
at each level of recursion.

Which ever of the two approaches is taken, we can ask which version
(stack or queue) needs less memory resource.  It turns out that in
some pathological cases the queue version does a better job, and
AFAIK never does appreciably worse.  Also I believe (based on a
less than fully reliable memory) that the queue version does a bit
better in "typical" cases.  I don't have a reason to offer as to
why these results should be so, only that empirically that's what
I've seen.

Hopefully that is enough elaboration. :)