[R] Problem with nested functions - functions nested too deeply in source code
Duncan Murdoch
murdoch.duncan at gmail.com
Fri May 7 15:53:55 CEST 2010
Maximilian Kofler wrote:
> Duncan Murdoch <murdoch.duncan <at> gmail.com> writes:
>
>
>
>> I doubt if that was the error message. More likely you saw
>>
>> Error: evaluation nested too deeply: infinite recursion /
>> options(expressions=)?
>>
>
> Exactly this was the error message I recieved
>
>
>> This isn't a case of the source being nested to deeply, but rather of the
>> evaluation being nested too deeply.
>> This happens in recursive algorithms when R runs out of
>> stack space, around 5000 calls deep. Is it likely in your dataset that
>> a recursion depth of 5000 is reasonable? In most cases this indicates a
>> programming error that leads to an infinite recursion, but there are
>> probably cases where a depth like that is reasonable.
>>
>
> I don't think that it is a programming error, because I succeyyfully
> calculated subgraph isomirphism with the algorithm, but with
> smaller input graphs.
The programming error might be in the design, not the implementation.
For example, you can sum a vector like this:
badSum <- function(x) {
if (length(x) > 1) x[1] + badSum(x[-1])
else x
}
and you'll get the right result for vectors of lengths from 1 up to
around length 5000, but not for bigger ones. The solution in some
languages is to recognize when recursion is being used unnecessarily and
to optimize it away, but R doesn't do that. So the programmer has to
recognize when recursion isn't really needed and rewrite the function to
work without it. For example, in the case above, we don't need x after
extracting x[1], so there's no need to make a new call to badSum (which
preserves it). Just turn it into a loop:
notsobadSum <- function(x) {
result <- x[1]
while (length(x) > 1) {
x <- x[-1]
result <- result + x[1]
}
result
}
(This is still a bad way to compute a sum in R, it is just a simple
illustration).
> So the algorithm seems to work.
> I already tried to set options(expressions=500000), but
> then I cause a protection stack overflow:
>
> error: protect(): protection stack overflow
>
> Is the problem that too many objects are stored in the stack?
>
Too many stack frames. You're not running out of memory, you're running
out of a particular type of memory. When you set expressions to 500000
you just started to run out of a different resource. The help page
?options tells you how to work around that one, but I suspect you really
need to rewrite your functions so they only recurse
when they need to.
Duncan Murdoch
> If yes, somebody knows how to solve this
> problem?
>
> thanks for your replies
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
More information about the R-help
mailing list