[R] extremely slow recursion in R?
MARK LEEDS
markleeds at verizon.net
Thu Aug 24 22:21:15 CEST 2006
i'm sure someone else will explain the recursion issue but , as far as your
program running a few days, you don't have to wait this long. if you are in
windows and do
a ctrl alt delete and then click on processes, if the memory usage being
used by that R process is staying EXACTLY the same and not moving at all,
this is a sign
( atleast i have found this to be true for my cases. i guess it may not
always hold ) that nothing is happening and your job has gone into never
never land or has somehow become frozen.
----- Original Message -----
From: "Jason Liao" <jg_liao at yahoo.com>
To: <r-help at stat.math.ethz.ch>
Sent: Thursday, August 24, 2006 4:05 PM
Subject: [R] extremely slow recursion in R?
>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