# [R] extremely slow recursion in R?

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

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