[R] extremely slow recursion in R?

[Joerg van den Hoff]

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