Re: Finding the set of recursive calls

"Martin Ward" <Martin.Ward@durham.ac.uk>
24 Jul 2002 02:21:12 -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)
Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-08-10)
Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-08-10)
[1 later articles]
| List of all articles for this month |
From: "Martin Ward" <Martin.Ward@durham.ac.uk>
Newsgroups: comp.compilers
Date: 24 Jul 2002 02:21:12 -0400
Organization: Compilers Central
Keywords: analysis
Posted-Date: 24 Jul 2002 02:21:12 EDT

> Given complete call information, is there an algorithm to determine
> which functions can be called recursively ?

A function can be called recursively if there is a path from
the function to itself in the call graph. So your question reduces
to a reachability problem in the call graph (is A reachable from A?).
Reachability can be solved in linear time, so you can find the set
of all recursive functions in no more than quadratic time.

Martin

Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/

Post a followup to this message

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