[R] extremely slow recursion in R?

Jason Liao jg_liao at yahoo.com
Thu Aug 24 22:05:12 CEST 2006

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.


R code

my.choose = function(n,k)
  if(k>n) value = 0.
  else if(k==0) value = 1.
  else if(k==n) value = 1.
  else value = my.choose(n-1,k) + my.choose(n-1, k-1)



Fortran code

  recursive function choose(n, k) result(value)
  implicit none
  integer n, k
  double precision value
  if(k>n) then
    value = 0.
  elseif(k==0) then
    value = 1.
  else if(k==n) then
    value = 1.
    value = choose(n-1, k) + choose(n-1, k-1)
  end if
  end function
  program main
    write(*,*) choose(30, 15)
  end program

Jason Liao, http://www.geocities.com/jg_liao
Department of Epidemiology and Biostatistics
Drexel University School of Public Health
245 N. 15th Street, Mail Stop 660
Philadelphia, PA 19102-1192
phone 215-762-3934

More information about the R-help mailing list