Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #10615

Re: Iterate over the adjacent elements in a matix container

Show all headers | View raw

On 9/30/11 2:24 AM, Juha Nieminen wrote:
> Richard Damon<news.x.richarddamon@xoxy.net>  wrote:
>> One problem with a depth-first search done this way is you will need a
>> recursion depth equal to the maximum number of nodes that may need to be
>> marked. A breadth first search, using a stack like structure to store
>> the list of nodes to visit, may require less levels stored, and if using
>> tail recursion optimization, doesn't actually need to use recursion.
>
>    Btw, I didn't notice this at first, but now I see that you seem to be
> suggesting that it's much preferable to avoid recursion, even if it means
> using a more complicated (to implement) solution. Why?
>
>    Note that by using a stack you are not really saving any memory. You
> will still be storing O(n) amount of data (where n is the number of nodes
> that have to be marked). In fact, depending a bit on the situation, the
> breadth-first search may end up storing more data than the depth-first
> search (although it's true that in some cases it may be the other way
> around).
>
>    Anyways, your concern seems to not be the amount of data needed to
> perform the task, but the recursion. Why? What exactly is the problem?


Note that there are a couple of issues here. One is that a level of 
recursion cost a lot more memory space than saving a few locations to 
iterate in a program controlled resource than a recursive call. Remember 
that a level of recursion is going to create new copies of every 
automatic variable used in the function, as opposed to just what is 
needed to keep track locations to be filled.

A second issue is that recursion grows the program stack space, and 
there is no way (portably) of checking for program stack overflow, while 
you can check for running out of memory in the heap or program defined 
memory structure. (Not every program runs on machines with gigabytes of 
RAM).

Also, in typical worse case type configurations, a depth first path is 
going to trace down to a significantly higher depth than a breadth first 
search, as after you run out to what would seem to be a maximum distance 
away, the depth first search will turn around and come back and 
eventually hit most of the open cells in a deep path, it may 
occasionally trap it self, but after it backs out a few steps, it will 
find the deeper path. For a 200x200 flood file, I would expect it to get 
at least 30,000 levels deep. On the other hand, a breadth first search 
will tend to generate an expanding ring only a couple of cells thick, 
needing maybe 1600 locations recorded at a given time for the same area. 
The key here is that breadth first limits itself to first looking near 
where it has done work, and finishes cells, so we don't need to revisit 
them. Depth first can't tell that a later path will get to a cell at a 
shorted depth. This is a common issue with traversing highly connected 
paths.

There is nothing inherently wrong with recursion, but it isn't always 
the right tool, and often is a somewhat heavy handed one. An important 
thing when using recursion is to make sure that it does terminate, and 
in a reasonable number of levels. Removing recursion and replacing it 
with iteration is a common optimization. (For an extreme case compare 
recursive and iterative version of factorial or Fibonacci calculations).

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Iterate over the adjacent elements in a matix container Alexander <alvatov@gmail.com> - 2011-09-26 12:44 -0700
  Re: Iterate over the adjacent elements in a matix container Victor Bazarov <v.bazarov@comcast.invalid> - 2011-09-26 15:49 -0400
  Re: Iterate over the adjacent elements in a matix container puppi <fabricio.puppi@gmail.com> - 2011-09-26 15:30 -0700
  Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-09-27 06:43 +0100
    Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 07:12 +0000
      Re: Iterate over the adjacent elements in a matix container Richard Damon <news.x.richarddamon@xoxy.net> - 2011-09-27 11:10 -0400
        Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 20:32 +0000
        Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-30 06:24 +0000
          Re: Iterate over the adjacent elements in a matix container Nobody <nobody@nowhere.com> - 2011-09-30 20:55 +0100
          Re: Iterate over the adjacent elements in a matix container Richard Damon <news.x.richarddamon@xoxy.net> - 2011-09-30 17:07 -0400
  Re: Iterate over the adjacent elements in a matix container Krice <paulkp@mbnet.fi> - 2011-09-27 03:37 -0700
  Re: Iterate over the adjacent elements in a matix container Alexander <alvatov@gmail.com> - 2011-09-29 10:47 -0700
    Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-09-30 01:28 +0100
    Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-30 06:19 +0000
    Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-10-02 05:16 +0100
      Re: Iterate over the adjacent elements in a matix container "Paul" <pchrist<nospam>or@yahoo.co.uk> - 2011-10-03 05:31 +0100
        Re: Iterate over the adjacent elements in a matix container "Paul" <pchrist<nospam>or@yahoo.co.uk> - 2011-10-03 05:47 +0100

csiph-web