Re: non recursive algorithm for depth first numbering

I don't know any details about what you're doing, but as a rule of
thumb -- you can always make recursion to be a loop. However, you
won't get rid of some sort of "storage" completely you can
significantly reduce amount of memory used by storing in a heap ( or
equivalent ) only those data items you really need, instead of wasting
stack for procedure's frame and "useless" local variables.


On the other hand, if you have such "deep" recursion you might want to
consider changing algorithm, as well. Again, it all depends on your
requirements.


Thanks,
Roman.


On 3 Dec 2001 20:25:39 -0500, Jeremy Wright wrote:
>Is there a non recursive algorithm to do depth first numbering, or
>optimizations to the standard algorithm (as in Dragon 2, pp 662) that
>reduce the amount of recursion.
>
>The issue arises as I am processing the basic block graph for a
>perform range in Cobol. The graph can be extremely big. Additionally,
>perform statements occur in a basic block by themselves (to allow
>optimizations across performs, and into/out of perform ranges). This
>causes the depth of the graph to be orders of magnitude greater than
>would otherwise be the case.
[Making the recursion stack explicit would certainly speed up the
recursion, but I suspect that in this case it'd be more productive to
look for ways to abstract stuff out at the paragraph level or higher
to avoid much of the recursion altogether. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.