如何在R中編寫遞歸函數？

Question

如何寫一個遞歸函數來獲得R中組合（n，r）=組合（n-1，r-1）+組合（n-1，r）？ 我試着下面的代碼，但我只得到一個錯誤信息：

nCr=function(n, r) { 
if (r == 0) 
{ 
if (r == n) { 

return (1) 
} } else { 
return (nCr(n-1, r-1) + nCr(n-1, r)) 
} 
} 

謝謝！

Answer 1

相關問題：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 

請注意內置函數的性能。

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 

性能問題部分發生，因爲函數被多次調用相同的輸入。通過緩存結果可以使nCr速度更快‐儘管注意到內置函數仍然快得多，但此技術對於許多遞歸函數很有用。

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