[R] [R-sig-hpc] recursion depth limitations

[Simon Urbanek]

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