[R] Problem with nested functions - functions nested too deeply in source code

[Duncan Murdoch]

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