[R] extremely slow recursion in R?

Joerg van den Hoff j.van_den_hoff at fz-rossendorf.de
Fri Aug 25 13:52:04 CEST 2006


Thomas Lumley wrote:
> 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
>

maybe someone's interested:
I made the same observation of seemingly very slow recursion recently: 
just for fun I used the (in)famously inefficient

fib <- function(n = 1) {
    if (n < 2)
       fn <- 1
    else
       fn <- fib(n - 1) + fib(n - 2)
    fn
}

for calculating the fibonacci numbers and compared `fib(30)' (about 
1.3e6 recursive function calls ...) to some other languages (times in sec):

language  time
==============
C          0.034  (compiled, using integers)
Ocaml      0.041  (compiled, using integers)
Ocaml      0.048  (interpreted, using integers)
C          0.059  (compiled, using floats)
Lua        1.1
ruby       3.4
R          21
octave    120

apart from octave (which seems to have a _real_ issue with recursive 
function calls), R is by far the slowest in this list and still a factor 
7-20 slower than the interpreter based Lua and ruby. the speed loss 
compared to C or Ocaml is about a factor of 350-600 here (Ocaml keeps 
its speed more or less in this simple example even in 'script mode', 
which is remarkable, I think (and it usually loses only a factor of 
about 7 or so in script mode compared to the compiled variant)

for the specialists the bad performance of R in this situation might not 
be surprising, but I was not aware that recursive function calls are 
seemingly as expensive as explicit loops (where the execution time ratio 
of R to C again is of the same order, i.e. =~ 400).

of course, such comparsions don't make too much sense: the reason to use 
R will definitely not be its speed (which, luckily, often does not 
matter), but the combination of flexible language, the number of 
available libraries and the good 2D graphics.



joerg



More information about the R-help mailing list