[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.
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
More information about the R-help
mailing list