24 Jul 2002 02:21:12 -0400

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] |

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.