# Re: Finding the set of recursive calls

## "Hans Aberg" <haberg@matematik.su.se>24 Jul 2002 01:48:58 -0400

From comp.compilers

Related articles
Finding the set of recursive calls jeremy.wright@microfocus.com (Jeremy Wright) (2002-07-21)
Re: Finding the set of recursive calls haberg@matematik.su.se (Hans Aberg) (2002-07-24)
Re: Finding the set of recursive calls dietz@dls.net (Paul F. Dietz) (2002-07-24)
Re: Finding the set of recursive calls Martin.Ward@durham.ac.uk (Martin Ward) (2002-07-24)
Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-07-24)
Re: Finding the set of recursive calls jeremy.wright@microfocus.com (Jeremy Wright) (2002-07-25)
Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-07-31)
Re: Finding the set of recursive calls haberg@matematik.su.se (Hans Aberg) (2002-08-04)
[3 later articles]
| List of all articles for this month |

 From: "Hans Aberg" Newsgroups: comp.compilers Date: 24 Jul 2002 01:48:58 -0400 Organization: Mathematics References: 02-07-084 Keywords: analysis Posted-Date: 24 Jul 2002 01:48:58 EDT

<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>
* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message