R help - Sep 2009 - Recursion is slow

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

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.

Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com  
> -----Original Message-----
> From: r-help-bounces at r-project.org 
> [mailto:r-help-bounces at r-project.org] On Behalf Of Bryan Keller
> Sent: Thursday, September 03, 2009 2:11 PM
> To: r-help at r-project.org
> Subject: [R] Recursion is slow
> 
> 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)
> }
> 
For starters, remove all repeated calculations from
the for loop.  Then vectorize the length(T)==2 case
to avoid a lot of calls to the scalar case.  Finally,
I noticed that the answer was independent of the
order of T and that putting it in reverse sorted order
was the faster order, so I did that.  I use default
values of arguments so you don't have to supply
derived values when you start but the recursions
don't have to recompute some things.

B <- function(T,m,lt=length(T), Tsorted = rev(sort(T))) {
   if (lt == 1L) {
      R <- as.integer(m <= Tsorted && 0L <= m)
   } else if (lt == 2L) {
      mu <- m - (0:Tsorted[2L])
      R <- sum(mu <= Tsorted[1L] & 0L <= mu)
   } else {
      R <- 0L
      lt1 <- lt-1L
      T1 <- Tsorted[1:lt1]
      for (mu in m-(0:Tsorted[lt])) {
         R <- R + B(unused, mu, lt1, T1)
      }
   }
   R
}

E.g.,
> system.time(A( c(20,40,35,21,31), 100))
   user  system elapsed 
  13.23    0.08   12.93 
> system.time(B( c(20,40,35,21,31), 100))
   user  system elapsed 
   0.35    0.00    0.33 
> A( c(20,40,35,21,31), 100)
[1] 193363
> B( c(20,40,35,21,31), 100)
[1] 193363

Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com 
> -------------
> 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.
>