Stack level too deep

[marcus]

I have a tree that I do recursion over the nodes (and then some
recursion inside the nodes...). Two problems:

1) Stack level too deep (error message)
2) Speed get really really lousy when the tree is deep. With a small
shallow tree the speed is nice. I get that the overall time get long but
the handling of each node is slow in a deep tree.

Any way around these issues? I should say that it's running in a Rails
environment on Win, Ruby 1.8.2

/Marcus

 

[Meinrad Recheis]

------=_Part_5413_27465885.1141111583781
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I have a tree that I do recursion over the nodes (and then some
recursion inside the nodes...). Two problems:

1) Stack level too deep (error message)

what is the maximum depth of the tree? and how do you traverse it?
-- henon

------=_Part_5413_27465885.1141111583781--

 

[Robert Klemme]

I have a tree that I do recursion over the nodes (and then some
recursion inside the nodes...). Two problems:

1) Stack level too deep (error message)
2) Speed get really really lousy when the tree is deep. With a small
shallow tree the speed is nice. I get that the overall time get long
but the handling of each node is slow in a deep tree.

Any way around these issues? I should say that it's running in a Rails
environment on Win, Ruby 1.8.2

The easiest change is to use BFS instead of DFS - if that's possible in
your scenario. Alternatives:

- implement a DFS with your own kind of stack

- change the way you store things to avoid such a deep recursion

Also, I guess you made sure that there is no loop, i.e. the structure is
actually a tree...

Kind regards

robert

 

[Meinrad Recheis]

------=_Part_7129_14867535.1141123839399
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

- change the way you store things to avoid such a deep recursion

[...]

i now remember that i had a similar problem with a deep recursion and stack
depth. i solved
it by converting the recursive function into a while loop. you can transfor=
m
every recursion
into a loop, but it will not be as easy to read anymore.
-- henon

------=_Part_7129_14867535.1141123839399--

 

[Robert Klemme]

- change the way you store things to avoid such a deep recursion

[...]

i now remember that i had a similar problem with a deep recursion and
stack depth. i solved
it by converting the recursive function into a while loop. you can
transform every recursion
into a loop, but it will not be as easy to read anymore.

That's exactly the other recommendation I gave.

robert

 

[marcus]

Robert Klemme skrev:

- change the way you store things to avoid such a deep recursion

[...]

i now remember that i had a similar problem with a deep recursion and
stack depth. i solved
it by converting the recursive function into a while loop. you can
transform every recursion
into a loop, but it will not be as easy to read anymore.

That's exactly the other recommendation I gave.

robert

I haven't received the other mail(s) that is talked about. However:

I'm implementing the composite pattern using acts_as_tree and STI in
ActiveRecord. The thing that is modeled is nodes in a web site structure
that is kind of tree structured (isn't all web sites?). So I try to loop
over the nodes to do various operations (generate navigations, publish,
distribute etc).

I'm sure that there are ways around this but then you have to code
around stuff because of the language implementation and that doesn't
feel good at all...

/Marcus

 

[Logan Capaldo]

--Apple-Mail-8--364783872
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

I'm sure that there are ways around this but then you have to code
around stuff because of the language implementation and that
doesn't feel good at all...

Well maybe you can take smaller steps to coding around the
implementation, first code a tail-recursive version and then convert
that into an iterative version.


--Apple-Mail-8--364783872--

 

[Eric Christensen]

1) Stack level too deep (error message)

You can change the stack size of the Ruby executable with editbin. It's
part of Visual Studio.