[R] Re cursion is slow

[Ben Bolker]

Bryan Keller wrote:
> 
> The following recursion is about 120 times faster in C#.  I know R is not
> known for its speed with recursions but I'm wondering if anyone has a tip
> about how to speed things up in R.
> 
> #"T" is a vector and "m" is a number between 1 and sum(T)
> 
> A <- function(T,m) {
> lt <- length(T)
> 
> if (lt == 1) {
> 	if (0 <= m & m <= T[1]) {
> 		return(1)
> 		} else {
> 		return(0)
> 	}
> }
> R <- 0
> for (u in 0:T[lt]) {
> 	R <- (R+(A(T[1:(lt-1)],(m-u))))
> 	}
> return(R)
> }
> 
> -------------
> Bryan Keller, Doctoral Student/Project Assistant
> Educational Psychology - Quantitative Methods
> The University of Wisconsin - Madison
> 
> ______________________________________________
> R-help at r-project.org 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.
> 
> 

Can anyone tell me why my version takes TWICE AS LONG (to my surprise)?


A0 <- function(T,m) {
  lt <- length(T)

  if (lt == 1) {
    if (0 <= m & m <= T[1]) {
      return(1)
    } else {
      return(0)
    }
  }
  R <- 0
  for (u in 0:T[lt]) {
    R <- (R+(A0(T[1:(lt-1)],(m-u))))
  }
  return(R)
}

A1 <- function(T,m) {
  lt <- length(T)

  if (lt == 1) {
    return(as.numeric(0 <= m & m <= T[1]))
  }
  sum(sapply(m-(0:T[lt]),A1,T=T[-lt]))
}

system.time(a0 <- A0(1:8,20)) ## about 5 secs
system.time(a1 <- A1(1:8,20)) ## about 11 secs

-- 
View this message in context: http://www.nabble.com/Recursion-is-slow-tp25284189p25284359.html
Sent from the R help mailing list archive at Nabble.com.