[R] extremely slow recursion in R?

From: Jason Liao <jg_liao_at_yahoo.com>
Date: Fri 25 Aug 2006 - 06:05:12 EST


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.

Jason

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)

  value
}

print(date())
my.choose(30,15)
print(date())

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.
  else
    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



R-help@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. Received on Fri Aug 25 06:12:38 2006

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.1.8, at Fri 25 Aug 2006 - 10:27:49 EST.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.