Re: Detecting endless recursion?

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.

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