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