How can I write a recursive function in R?

Question

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!

Which type of error message do you get? It seems that you try to use the function you define in its definition... — llrs, Feb 11 '14 at 10:11
@Llopis Well, that kinda **is** the definition of a recursive function! — Carl Witthoft, Feb 11 '14 at 12:56

score 9 · Accepted Answer · edited May 23 '17 at 11:33

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 &dash; 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

How can I write a recursive function in R?

1 Answers1