[R] extremely slow recursion in R?

Damien Moore damien.moore at excite.com
Fri Aug 25 16:28:23 CEST 2006

i tried fib(30):

R: 8.99s
Python (interpreted): 0.96s
Python (interpreted but using psyco library): 0.03s
C++: 0.015s


 --- On Fri 08/25, Joerg van den Hoff < j.van_den_hoff at fz-rossendorf.de > wrote:
From: Joerg van den Hoff [mailto: j.van_den_hoff at fz-rossendorf.de]
To: tlumley at u.washington.edu
     Cc: jg_liao at yahoo.com, r-help at stat.math.ethz.ch
Date: Fri, 25 Aug 2006 13:52:04 +0200
Subject: Re: [R] extremely slow recursion in R?

Thomas Lumley wrote:<br>> On Thu, 24 Aug 2006, Jason Liao wrote:<br>> <br>>> I recently coded a recursion algorithm in R and ir ran a few days<br>>> without returning any result. So I decided to try a simple case of<br>>> computing binomial coefficient using recusrive relationship<br>>><br>>> choose(n,k) = choose(n-1, k)+choose(n-1,k-1)<br>>><br>>> I implemented in R and Fortran 90 the same algorithm (code follows).<br>>> The R code finishes 31 minutes and the Fortran 90 program finishes in 6<br>>> seconds. So the Fortran program is 310 times faster. I thus wondered if<br>>> there is room for speeding up recursion in R. Thanks.<br>>><br>> <br>> Recursive code that computes the same case many times can often be sped up <br>> by memoization, eg<br>> <br>> memo<-new.env(hash=TRUE)<br>> chewse<-function(n,k) {<br>>      if (n==k) return(1)<br>>      if(k==1) return(n)<br>> <br>>      if(exists(paste(n,k),memo,inherits=FALSE))<br>>          return(get(paste(n,k),memo))<br>>      
rval<-chewse(n-1,k)+chewse(n-1,k-1)<br>>      assign(paste(n,k),rval,envir=memo)<br>>      return(rval)<br>> }<br>> <br>> This idea was discussed in an early Programmers' Niche article by Bill <br>> Venables in R News.<br>> <br>> However, I'm surprised that you're surprised that compiled Fortran 90 is <br>> 310 times faster than interpreted R.  That would be about what I would <br>> expect for code that isn't making use of vectorized functions in R.<br>> <br>> <br>>  	-thomas<br>><br><br>maybe someone's interested:<br>I made the same observation of seemingly very slow recursion recently: <br>just for fun I used the (in)famously inefficient<br><br>fib <- function(n = 1) {<br>    if (n < 2)<br>       fn <- 1<br>    else<br>       fn <- fib(n - 1) + fib(n - 2)<br>    fn<br>}<br><br>for calculating the fibonacci numbers and compared `fib(30)' (about <br>1.3e6 recursive function calls ...) to some other languages (times in sec):<br><br>language  time<br>==============<br>C         
 0.034  (compiled, using integers)<br>Ocaml      0.041  (compiled, using integers)<br>Ocaml      0.048  (interpreted, using integers)<br>C          0.059  (compiled, using floats)<br>Lua        1.1<br>ruby       3.4<br>R          21<br>octave    120<br><br>apart from octave (which seems to have a _real_ issue with recursive <br>function calls), R is by far the slowest in this list and still a factor <br>7-20 slower than the interpreter based Lua and ruby. the speed loss <br>compared to C or Ocaml is about a factor of 350-600 here (Ocaml keeps <br>its speed more or less in this simple example even in 'script mode', <br>which is remarkable, I think (and it usually loses only a factor of <br>about 7 or so in script mode compared to the compiled variant)<br><br>for the specialists the bad performance of R in this situation might not <br>be surprising, but I was not aware that recursive function calls are <br>seemingly as expensive as explicit loops (where the execution time ratio 
<br>of R to C again is of the same order, i.e. =~ 400).<br><br>of course, such comparsions don't make too much sense: the reason to use <br>R will definitely not be its speed (which, luckily, often does not <br>matter), but the combination of flexible language, the number of <br>available libraries and the good 2D graphics.<br><br><br><br>joerg<br><br>______________________________________________<br>R-help at stat.math.ethz.ch mailing list<br>https://stat.ethz.ch/mailman/listinfo/r-help<br>PLEASE do read the posting guide http://www.R-project.org/posting-guide.html<br>and provide commented, minimal, self-contained, reproducible code.<br>

More information about the R-help mailing list