# [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

```