Re: Detecting endless recursion?

John McEnerney <jmcenerney@austin.rr.com>
12 Jan 2004 13:34:24 -0500

          From comp.compilers

Related articles
Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-01-12)
Re: Detecting endless recursion? jmcenerney@austin.rr.com (John McEnerney) (2004-01-12)
Re: Detecting endless recursion? fjh@cs.mu.oz.au (Fergus Henderson) (2004-01-12)
Re: Detecting endless recursion? nmm1@cus.cam.ac.uk (2004-01-16)
Re: Detecting endless recursion? jgd@cix.co.uk (2004-01-16)
Re: Detecting endless recursion? derkgwen@HotPOP.com (Derk Gwen) (2004-01-16)
Re: Detecting endless recursion? torbenm@diku.dk (2004-01-16)
Re: Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-01-16)
[25 later articles]
| List of all articles for this month |

From: John McEnerney <jmcenerney@austin.rr.com>
Newsgroups: comp.compilers
Date: 12 Jan 2004 13:34:24 -0500
Organization: Road Runner High Speed Online http://www.rr.com
References: 04-01-050
Keywords: practice, debug
Posted-Date: 12 Jan 2004 13:34:24 EST

On 1/12/04 10:58 AM, in article 04-01-050@comp.compilers, "Uli Kusterer"
> [ how to deal with student programs that recurse forever ]


> [The limit you one is one deeper than the deepest program that's not stuck
> in a loop. My impression is that other than artifical examples like
> Ackerman's function, real code doesn't nest very deeply so an arbitrary
> limit like 100 deep shoulddo the trick. -John]


Yeah, I'm going to have to go ahead and disagree with you here.


There are real programs that will naively exceed 100 levels deep
without being stuck. For example, a program that does the obvious
recursive depth-first-search of a graph, where it is highly possible
to have nodes that just chain to other nodes, can easily exceed 100
levels of nesting.


(I said naive because of course there are trivial ways to eliminate this
behavior, but the first version one codes is almost always the naive one)


We hail from an era where 1MB was a lot of memory, but nowadays when
1GB is typical, I think we can afford to be less stingy. 10,000 is
probably safer than 100, but small enough that a well-coded
interpreter on a fast machine will still blow up quickly on infinite
recursion.



Post a followup to this message

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