[R] [R-sig-hpc] recursion depth limitations
Simon Urbanek
simon.urbanek at r-project.org
Fri Dec 14 13:46:51 CET 2012
On Dec 14, 2012, at 6:25 AM, Suzen, Mehmet wrote:
> On 14 December 2012 12:13, Suzen, Mehmet <suzen at acm.org> wrote:
>> On 13 December 2012 23:21, Rui Barradas <ruipbarradas at sapo.pt> wrote:
>>> But it does, each recursive call will load another copy of the function, and
>>> another copy of the variables used.
>>> In fact, the cost can become quite large since everything is loaded in
>>> memory again.
>>>
>>> Hope this helps,
>>>
>>
>> Many thanks for the replies.
>>
>> What about tail-recursion? I have seen that there were discussions
>> about this:
>>
>> https://stat.ethz.ch/pipermail/r-help/2006-April/102873.html
>>
>> Since it was 6 years ago, maybe now things are little different.
>
>
> Isn't it logical to translate any recursive function to tail-recursive
> internally? While tail-recursive
> version returns a value but the operation is essentially the same. I don't know
> how difficult to do it generically but maybe there is an advantage of
> keeping recursion
> as it is. What would that advantage be?
>
> For example, tail recursion would run but not the recursive version:
>
>> options(expressions=500000)
>> f <- function(x) if(x >0) f(x-1);
>> system.time(f(10000000))
> Error: C stack usage is too close to the limit
> Error: C stack usage is too close to the limit
>> f1<-function(x) x-1
>> f <- function(x) f1(x);
>> system.time(f(10000000))
> user system elapsed
> 0 0 0
>
>
You may be a bit misinformed about with tail recursion means - it still needs to evaluate the function for each recursion step, the only difference is that in such special case there is no additional information that needs to be stored -- and you have also proven why it's not as simple as you think:
> f <- function(x) if(x >0) f(x-1)
> (f(100))
NULL
> f1<-function(x) x-1
> f <- function(x) f1(x);
> (f(100))
[1] 99
Your latter version doesn't actually do anything anywhere close to the recursion you defined. R doesn't have tail recursion elimination and as Thomas pointed out in the cited post it would break some existing things if it did (call frame introspection etc.). [Whether it would be ok to break it for the sake of optimization is another question]
Note that in all such cases you can easily write the problem in an iterative fashion (admittedly it is less elegant -- but if you are dealing with such deep structures chances are that you probably care about efficiency and to go native code anyway).
Cheers,
Simon
More information about the R-help
mailing list