[R] extremely slow recursion in R?

[Thomas Lumley]

On Thu, 24 Aug 2006, Jason Liao wrote:

> I recently coded a recursion algorithm in R and ir ran a few days
> without returning any result. So I decided to try a simple case of
> computing binomial coefficient using recusrive relationship
>
> choose(n,k) = choose(n-1, k)+choose(n-1,k-1)
>
> I implemented in R and Fortran 90 the same algorithm (code follows).
> The R code finishes 31 minutes and the Fortran 90 program finishes in 6
> seconds. So the Fortran program is 310 times faster. I thus wondered if
> there is room for speeding up recursion in R. Thanks.
>

Recursive code that computes the same case many times can often be sped up 
by memoization, eg

memo<-new.env(hash=TRUE)
chewse<-function(n,k) {
     if (n==k) return(1)
     if(k==1) return(n)

     if(exists(paste(n,k),memo,inherits=FALSE))
         return(get(paste(n,k),memo))
     rval<-chewse(n-1,k)+chewse(n-1,k-1)
     assign(paste(n,k),rval,envir=memo)
     return(rval)
}

This idea was discussed in an early Programmers' Niche article by Bill 
Venables in R News.

However, I'm surprised that you're surprised that compiled Fortran 90 is 
310 times faster than interpreted R.  That would be about what I would 
expect for code that isn't making use of vectorized functions in R.


 	-thomas

Thomas Lumley			Assoc. Professor, Biostatistics
tlumley at u.washington.edu	University of Washington, Seattle