# Finding the set of recursive calls

## "Jeremy Wright" <jeremy.wright@microfocus.com>21 Jul 2002 02:12:17 -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)
[4 later articles]
| List of all articles for this month |

 From: "Jeremy Wright" Newsgroups: comp.compilers Date: 21 Jul 2002 02:12:17 -0400 Organization: Micro Focus Keywords: analysis, question Posted-Date: 21 Jul 2002 02:12:16 EDT

Given complete call information, is there an algorithm to determine
which functions can be called recursively ? I have tried Google, but
it returns so many hits that it is unusable.

Detecting that recursion exists is easy. You simply construct a rooted
directed graph that represent the call graph. You then do a
depth-first numbering. The presence of a back edge indicates
recursion.

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.

I started with the observation that a function cannot be recursive if
either
a) it is a leaf
b) it only calls functions known to be non recursive

This suggested the following

Visit each node (function) in reverse depth first order
Removing a leaf nodes from the graph
If a node n has successor s such that Dfn(n) > Dfn(s) carry on
Otherwise node n and all it descendants are recursive. Mark and
delete

However - this does not work in the case where a calls b, b calls c,
and c calls a and b.

I am sure this must be a well known problem, which has a solution. Can
anyone point me to a reference.

Thanks

Post a followup to this message