# Re: non recursive algorithm for depth first numbering

## vugluskr@unicorn.math.spbu.ru (Roman Shaposhnick)7 Dec 2001 23:38:39 -0500

From comp.compilers

Related articles
non recursive algorithm for depth first numbering jeremy.wright@merant.com (Jeremy Wright) (2001-12-03)
Re: non recursive algorithm for depth first numbering vugluskr@unicorn.math.spbu.ru (2001-12-07)
| List of all articles for this month |

 From: vugluskr@unicorn.math.spbu.ru (Roman Shaposhnick) Newsgroups: comp.compilers Date: 7 Dec 2001 23:38:39 -0500 Organization: St.Petersburg University References: 01-12-011 Keywords: analysis, comment Posted-Date: 07 Dec 2001 23:38:39 EST X-Comment-To: Jeremy Wright

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]

Post a followup to this message