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

[Suzen, Mehmet]

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