Re: Finding the set of recursive calls

<jeremy.wright@microfocus.com> wrote:


>Given complete call information, is there an algorithm to determine
>which functions can be called recursively ?
...
>Calculating the set of functions that are recursive is not so simple.
>This is not the same problem as finding loops, because loops require
>the head of the edge to dominate the tail. This is not a requirement
>for call recursion.


For a directed graph, one can compute the strongly connected components
(SCC's) using Tarjan's algorithm, see for example
        http://www1.ics.uci.edu/~eppstein/161/960220.html#sca
This is the most efficient possible, visiting each vertex and edge exactly once.


Possibly, you need a version for a undirected graph. But to every
undirected graph, one can associate a directed graph with two arrows the
opposite direction for every undirected edge. Then the SCC's of the
directed graph are the same as the connectivity components of the
undirected one. So it is perhaps not so difficult.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

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