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