Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 alpha 4/15/85; site kestrel.ARPA
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!decwrl!Glacier!kestrel!king
From: king@kestrel.ARPA
Newsgroups: net.lang
Subject: Re: Recursion
Message-ID: <1124@kestrel.ARPA>
Date: Sat, 14-Sep-85 22:00:08 EDT
Article-I.D.: kestrel.1124
Posted: Sat Sep 14 22:00:08 1985
Date-Received: Tue, 17-Sep-85 04:42:22 EDT
References: <250@mot.UUCP> <4302@alice.UUCP>
Organization: Kestrel Institute, Palo Alto, CA
Lines: 23

In article <4302@alice.UUCP>, ark@alice.UucP (Andrew Koenig) writes:
> >>     I think that would be a good idea, but wouldnt it be limited to direct
> >> recursion ( i.e. routine A calls A as apposed to A calls B, B calls A ). I
> >> don't know PL/I, but I would think including such a check for anything other
> >> than direct recursion would be a royal pain for a compiler writter.
> >> 
> > Actually, it's not too bad.  You just set up an n-by-n Boolean matrix
> > where n is the number of subroutines under consideration and the
> > ij element is 1 iff routine i calls routine j.  Then take the
> > transitive closure by Warshall's algorithm.  1's on the diagonal of
> > the result indicate which routines are indirectly recursive.
> 
> This uses up memory proportional to the square of the
> number of subroutines.  Not a good idea.

Yes, but the proportionality constant is very unimpressive.  A 1K by
1K is a million bits, which is nothing.  Surely nobody would put 1000
functions in one compilation!

You probably have to assume that all external procedures that call
external procedures are recursive...


-dick


Brought to you by Super Global Mega Corp .com