[net.lang] Recursion

ray (03/23/83)

I have probably come into this discussion very late, but anyway I have always
thought the best example of recursion is the definition of factorial:-

function fact(n);
  if n=0 then 1 else n*fact(n-1) close
end

The language by the way is POP-2, and that introduces a whole new discussion...

billw (04/09/83)

#R:micomvax:-12600:sri-unix:13600002:000:199
sri-unix!billw    Apr  7 18:32:00 1983

function fact(n);
  if n=0 then 1 else n*fact(n-1) close
end

Why does everyone do this?  Whats wrong with:

  if n=2 then 2 else n*fact(n-1) close

saves you two whole levels of recursion...

BillW

billw (04/09/83)

#R:micomvax:-12600:sri-unix:13600003:000:157
sri-unix!billw    Apr  7 18:38:00 1983

gulp, make that 1, instead of 2, or fact(1) wont work. (if fact(0)
is really defined, I guess that explains the "standard" definition)

Foot in Mouth
Bill W

bhayes (04/09/83)

#R:micomvax:-12600:sri-unix:13600004:000:53
sri-unix!bhayes    Apr  8 20:41:00 1983

Or how about

if n=5 then 120 else n*fact(n-1)

huh?

mat (04/10/83)

Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Re: Recursion  ???

(See title)
						Mark Terribile
						Duke of deNet

debray (04/11/83)

what? and why, for that matter, not

	if n=127 then _____ (whatever 127! is)
		 else n*fact(n-1) ?

mmr (04/11/83)

re:
    " if n=5 then 120 else n*fact(n-1) "

then how do you define the factorial of 2, which is perfectly valid? huh?

student (04/15/83)

Actually factorial(n) should be 

if(n<=1)
	then return (1);
else
	return n * factorial (n - 1)

since negative numbers factorials equals one also.

#ifdef flame
DON'T, DON'T, DON'T flame me about gamma functions. I DON'T want
to talk about them!!!!
#end flame

franka@mmintl.UUCP (Frank Adams) (08/27/85)

Concerning the recent discussion of FORTRAN and recursion: I think recursive
routines should have to be declared as such, as in (gasp) PL/I.  Not because
of efficiencies gained by knowing when a routine is recursive, but as an aid
in writing correct code.  I believe that making an inadvertent recursive call
(which generally results in a semi-infinite loop) is a not-uncommon error,
and that it is unusual to make a correct recursive call without being aware
that that is what one is doing.

Of course, I also like PASCAL ...

dik@zuring.UUCP (08/31/85)

In article <624@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes:
>
>Concerning the recent discussion of FORTRAN and recursion: I think recursive
>routines should have to be declared as such, as in (gasp) PL/I.  Not because
>of efficiencies gained by knowing when a routine is recursive, but as an aid
>in writing correct code.  ...

Of course, but in than case you have a new problem.  The system should check
whether the routine you declared as non-recursive is non-recursive indeed.
(What about routine 1 calling routine 2; which in turn calls routine 1.
I have had uses for this in a non-recursive way.)
Moral: a system (or a language) should never require things it is not
able to ckeck (like Fortran).
-- 
dik t. winter, cwi, amsterdam, nederland
UUCP: {seismo|decvax|philabs}!mcvax!dik

scott@gitpyr.UUCP (Scott Holt) (08/31/85)

In article <624@mmintl.UUCP>, franka@mmintl.UUCP (Frank Adams) writes:
> 
> Concerning the recent discussion of FORTRAN and recursion: I think recursive
> routines should have to be declared as such, as in (gasp) PL/I.  Not because
> of efficiencies gained by knowing when a routine is recursive, but as an aid
> in writing correct code.  I believe that making an inadvertent recursive call
> (which generally results in a semi-infinite loop) is a not-uncommon error,
> and that it is unusual to make a correct recursive call without being aware
> that that is what one is doing.
> 

    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.

                             - Scott.

-- 
---------
Where we are going and from whence we came are completly unknown to us...
and personaly, I have no idea where I am now.

Scott Holt
Georgia Tech Po Box 36199
Atlanta, GA 30332

...!{akgua,allegra,amd,hplabs,ihnp4,masscomp,ut-ngp}!gatech!gitpyr!scott
...!{rlgvax,sb1,uf-cgrl,unmvax,ut-sally}!gatech!gitpyr!scott

                        I WANT MY MTV!

debray@sbcs.UUCP (Saumya Debray) (09/03/85)

Scott Holt:
>
>     I think [compile-time checking of whether a procedure is recursive]
> 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.
> 
If we assume that a program doesn't have procedure/function variables (an
assumption that's true most of the time), then static checking of whether
or not a procedure can be recursive is straightforward, at least conceptually:
it's the transitive closure of the "can_call" relation, where "can_call(A,B)"
is true if routine A can directly call routine B.  (Of course, whether or
not routine A will _in_fact_ call routine B is undecidable.)
-- 
Saumya Debray
SUNY at Stony Brook

	uucp: {allegra, hocsd, philabs, ogcvax} !sbcs!debray
	arpa: debray%suny-sb.csnet@csnet-relay.arpa
	CSNet: debray@sbcs.csnet

franka@mmintl.UUCP (Frank Adams) (09/06/85)

In article <240@zuring.UUCP> dik@zuring.UUCP (Dik T. Winter) writes:
>>
>>Concerning the recent discussion of FORTRAN and recursion: I think recursive
>>routines should have to be declared as such, as in (gasp) PL/I.  Not because
>>of efficiencies gained by knowing when a routine is recursive, but as an aid
>>in writing correct code.  ...
>
>Of course, but in than case you have a new problem.  The system should check
>whether the routine you declared as non-recursive is non-recursive indeed.
>(What about routine 1 calling routine 2; which in turn calls routine 1.
>I have had uses for this in a non-recursive way.)

Well, yes, I also think the linker should check such things.  Along with
checking subprogram arguments for number, type, and direction...

al@mot.UUCP (Al Filipski) (09/10/85)

****Make my day, Line-Eater*****


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

--------------------------------
Alan Filipski, UNIX group, Motorola Microsystems, Tempe, AZ U.S.A
{seismo|ihnp4}!ut-sally!oakhill!mot!al
ucbvax!arizona!asuvax!mot!al
--------------------------------

mac@uvacs.UUCP (Alex Colvin) (09/11/85)

PL/I compilers descended from Multics PL/I do this kind of analysis.  PL/I
procedures are pretty messy, so there's good reason to optimize.

The transitive closure of a procedure call graph tells who calls whom.
This isn't too large, as PL/I has nested scopes, each of which tends to be
small.  External procedures are always considered potentially recursive.  A
procedure used for anything but a call (e.g. as a parameter or assigned to
a variable) are also potentially recursive. This turns out to do a good job.

ark@alice.UucP (Andrew Koenig) (09/11/85)

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

mr@hou2h.UUCP (M.RINDSBERG) (09/12/85)

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

This doesnt really use up memory.
Only during compilation.
It may take time, though.

					Mark

dik@zuring.UUCP (09/13/85)

In article <250@mot.UUCP> al@mot.UUCP (Al Filipski) writes:
(about A calling B calling A, and how to detect this)...
>	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.

No, the 1's indicate the routines that *might* be recursive, they
need not be.  (What in the situation that if A calls B, B will never
call A, vv.)
-- 
dik t. winter, cwi, amsterdam, nederland
UUCP: {seismo|decvax|philabs}!mcvax!dik

king@kestrel.ARPA (09/15/85)

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

franka@mmintl.UUCP (Frank Adams) (09/17/85)

In article <241@zuring.UUCP> dik@zuring.UUCP (Dik T. Winter) writes:
>(about A calling B calling A, and how to detect this)...
>
>No, the 1's indicate the routines that *might* be recursive, they
>need not be.  (What in the situation that if A calls B, B will never
>call A, vv.)

I have encountered this situation.  My feeling is that usually, it is the
result of sloppy design.  There are probably cases where it is legitimate,
however.

I would have no problem with labelling the routines A and B 'recursive'
in this case.  It is still true that if A calls B and B calls A, unless
it was recognized in the design that this would happen, it is nearly
certain that this is a bug.

tim@k.cs.cmu.edu.ARPA (Tim Maroney) (09/17/85)

"A million bits is nothing"?????  >120K is nothing?  Let's not be silly here.
-=-
Tim Maroney, Carnegie-Mellon University, Networking
ARPA:	Tim.Maroney@CMU-CS-K	uucp:	seismo!cmu-cs-k!tim
CompuServe:	74176,1360	audio:	shout "Hey, Tim!"

rcd@opus.UUCP (Dick Dunn) (09/18/85)

...discussion of detecting indirect recursion in compiler; response:
> 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 only detects potential indirect recursion.  As (I think) has been said
before, the facts that A calls B and B calls A do not together imply that A
and B are mutually recursive (but only that they might be).

By the way, don't forget that in traditional systems you also end up either
bagging the check across modules or building the transitive-closure
algorithm (PLUS figuring out "what is a procedure?") into your linker.
-- 
Dick Dunn	{hao,ucbvax,allegra}!nbires!rcd		(303)444-5710 x3086
   ...Lately it occurs to me what a long, strange trip it's been.

dik@zuring.UUCP (09/20/85)

In article <55@opus.UUCP> rcd@opus.UUCP (Dick Dunn) writes:
(No, not really...)
>> 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 only detects potential indirect recursion.  As (I think) has been said
>before, the facts that A calls B and B calls A do not together imply that A
>and B are mutually recursive (but only that they might be).
>
Furthermore, how do you decide which routine calls which?
The problem props up when pointers to subroutines and subroutines with
subroutine parameters are used.  You will have no knowledge of order
of assignment and use (where, when?).  So you will not see some
truly recursive routines.
-- 
dik t. winter, cwi, amsterdam, nederland
UUCP: {seismo|decvax|philabs}!mcvax!dik