[R-sig-hpc] [R] recursion depth limitations
Suzen, Mehmet
msuzen at gmail.com
Fri Dec 14 20:48:19 CET 2012
On 14 December 2012 13:46, Simon Urbanek <simon.urbanek at r-project.org> wrote:
> 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:
Thank you Simon for your time and patient reply. I was thinking
calling another function over again is called indirect recursion.
> 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.
I see what you mean. I was confused. My intention was having 100 calls
in the second one with f1 as well.
Maybe I can make the point with using another example via mutual
recursion, 'fibRping/pong' below.
But I was thinking 'fibRping' version would need less memory then the
plain recursion, which I now understand
that I was mistaken. Every call counts then. Even though I had an
impression that calling the same
function more then once like fibRping/pong would not create additional
memory requirement ... (Probably the issue is noting to do with
Rs internals though..
Using Dirk's blog entry (http://dirk.eddelbuettel.com/blog/2011/09/08/) :
## R implementation of recursive Fibonacci sequence
fibR <- function(n) {
if (n == 0) return(0)
if (n == 1) return(1)
return (fibR(n - 1) + fibR(n - 2))
}
# Now Mutual recursion
fibRping <- function(n) {
if (n == 0) return(0)
if (n == 1) return(1)
return (fibRpong(n - 1) + fibRpong(n - 2))
}
fibRpong <- function(n) {
if (n == 0) return(0)
if (n == 1) return(1)
return (fibRping(n - 1) + fibRping(n - 2))
}
options(expressions=500000)
fibR(50000)> options(expressions=500000)
> fibR(50000)
Error: C stack usage is too close to the limit
> fibRping(50000)
Error: C stack usage is too close to the limit
More information about the R-sig-hpc
mailing list