On Dec 14, 2012, at 6:25 AM, Suzen, Mehmet wrote: > On 14 December 2012 12:13, Suzen, Mehmet <su...@acm.org> wrote: >> On 13 December 2012 23:21, Rui Barradas <ruipbarra...@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 ______________________________________________ R-help@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.
