CODEWITHSUNDEEP
rrecursioncombinations
Titi90
Titi90

Reputation: 139

How can I write a recursive function in R?

How can I write a recursive function to obtain the combination(n,r) = combination(n-1, r-1) + combination(n-1,r) in R? I tried the following code but I only get an error message:

nCr=function(n, r) {
if (r == 0)
{
if (r == n) {
    
return (1)
} } else {
return (nCr(n-1, r-1) + nCr(n-1, r)) 
}
}

Thanks!

Upvotes: 1

Views: 4409

Answers (1)

tonytonov
tonytonov

Reputation: 25608

Related questions: one, two. 

nCr <- function(n, r) {
  if (r == 0 | r == n) return (1)
  else return (nCr(n-1, r-1) + nCr(n-1, r)) 
}

nCr(20, 6)
[1] 38760
choose(20, 6)
[1] 38760

Note the performance of the built-in function.

system.time(for(i in 1:10) nCr(20, 6))
##    user  system elapsed 
##    8.74    0.00    8.90 

system.time(for(i in 1:10) choose(20, 6))
##    user  system elapsed 
##       0       0       0

The performance problems partly occur because the function is called with the same inputs many time. You can make nCr faster by caching the results ‐ this technique is useful for many recursive functions, though notice that the built-in function is still much faster.

library(memoise)
nCr2 <- memoise(nCr)
system.time(for(i in 1:10) nCr2(20, 6))
##    user  system elapsed 
##    0.88    0.00    0.91

Upvotes: 9

Related Questions