# [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:

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:

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