Article View: comp.lang.prolog
Article #880Re: mutual recursion query
From: Saumya K. Debray
Date: Thu, 07 Jun 1990 13:01
Date: Thu, 07 Jun 1990 13:01
19 lines
1266 bytes
1266 bytes
Richard A. O'Keefe (ok@goanna.cs.rmit.oz.au) writes:
> In article <718@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) wrote
> in response to my question about transforming mutual recursion.
> The bottom line was that transforming mutual recursion into linear
> recursion permits the use of a transitive closure algorithm.
>
> The question is, when is this a good idea?
This is probably tangential to Richard's point, but there are transitive
closure algorithms that require O(log N) iterations to compute the
fixpoint, where the (semi)naive algorithm for fixpoint computation would
require O(N) iterations. (There is, however, some growth in code size.:-)
--
Saumya Debray CS Department, University of Arizona, Tucson
internet: debray@cs.arizona.edu
uucp: uunet!arizona!debray
Technical Details
Message-ID:
<21907@megaron.cs.arizona.edu>Path:
arc1-ca.pugleaf.net!utzoo!attcan!uunet!cs.utexas.edu!asuvax!noao!arizona!debrayReferences:
<4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP> <3164@goanna.cs.rmit.oz.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!cs.utexas.edu!asuvax!noao!arizona!debray From: debray@cs.arizona.edu (Saumya K. Debray) Newsgroups: comp.lang.prolog Subject: Re: mutual recursion query Summary: transitive closures Message-ID: <21907@megaron.cs.arizona.edu> Date: 7 Jun 90 13:01:35 GMT References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP> <3164@goanna.cs.rmit.oz.au> Organization: U of Arizona CS Dept, Tucson Lines: 19