[R] extremely slow recursion in R?
Gabor Grothendieck
ggrothendieck at gmail.com
Thu Aug 24 22:15:11 CEST 2006
There was some discussion here:
http://finzi.psych.upenn.edu/R/Rhelp02a/archive/73646.html
On 8/24/06, Jason Liao <jg_liao at yahoo.com> wrote:
> 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 at 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.
>
More information about the R-help
mailing list