R中加泰罗尼亚数字的递归方法

Recursive method for Catalan numbers in R

我正在尝试在 R 中编写一个函数,该函数接受输入 numb 并输出相应的加泰罗尼亚数字。 供您参考,加泰罗尼亚数字 的 递归公式是

C_0 = 1; 
C_n = {(4n - 2)*C_(n-1)}/(n+1)

我的代码如下,

catalan_num_recr <- function(numb){
  if (numb == 0){
    return(1)
  }
  else
    return(((4*numb-2)*catalan_num_recr(numb-1))/(numb+1))
}

当我运行函数时,我得到,

> catalan_num_recr(3)
[1] 5

这是正确的。

AIM:但是,我正在尝试查找某个范围内的加泰罗尼亚语数字, 我想找到类似 catalan_num_recr(1:10) 的内容。

问题:这不适用于我的功能,我收到以下警告,

Warning messages:
1: In if (numb == 0) { :
  the condition has length > 1 and only the first element will be used

还有很多错误的输出值,

> catalan_num_recr(1:15)
 [1] 1.000000 2.000000 2.500000 2.800000 3.000000 3.142857 3.250000
 [8] 3.333333 3.400000 3.454545 3.500000 3.538462 3.571429 3.600000
[15] 3.625000

谁能帮我修改我的function/or帮我看清问题?

此致。

使用 Vectorize 接受一个函数和 returns 一个新函数,它本质上是接受矢量化输入的函数的包装器。该计算实际上由 mapply 重复执行,因此它不会像编写一个手动向量化的函数那样快。

Vectorize(catalan_num_recr)(1:15)
 [1]       1       2       5      14      42     132     429    1430    4862
[10]   16796   58786  208012  742900 2674440 9694845

您的函数目前不接受矢量输入。这可能有点令人困惑,因为许多函数(例如数学运算符)默认情况下都是矢量化的。您需要使用 mapapply 函数将函数应用于向量的每个元素。这实际上是一个快速循环,purrr 包的优点是语法一致且类型稳定。

catalan_num_recr <- function(numb){
  if (numb == 0){
    return(1)
  }
  else
    return(((4*numb-2)*catalan_num_recr(numb-1))/(numb+1))
}

purrr::map_dbl(1:15, catalan_num_recr)
#>  [1]       1       2       5      14      42     132     429    1430
#>  [9]    4862   16796   58786  208012  742900 2674440 9694845

reprex package (v0.2.0) 创建于 2018-05-21。

您只需要使用像 apply 系列中的 sapply 这样的矢量化函数。

sapply(1:10,catalan_num_recr,USE.NAMES = F)

您可以在数字向量上使用 sapply(或 lapply

sapply(c(0:15), catalan_num_recr)

只需将输出放在数据框中,这样您就可以检查数字

data.frame("n" = c(0:5), "cnr" = sapply(c(0:5), catalan_num_recr))

  n cnr
1 0   1
2 1   1
3 2   2
4 3   5
5 4  14
6 5  42

首先,您收到的警告告诉您,在 numb == 0 中,R 将只计算 numb[1] == 0

虽然其他答案正确,但效率不高,因为您需要多次计算每个加泰罗尼亚数字。 (对于 Catalan(15),您需要计算 Catalan(14),您已经计算过了)

我认为这是一个更好的版本,它计算每个加泰罗尼亚数字直到最大数字,然后 returns 您要求的数字。

catalan <- function(numbs) {
   cat <- vector("numeric", length(max(numbs)) + 1)
   for (i in 0:max(numbs)) {
      if (i == 0) {
         cat[i+1] <- 1
      } else {
         cat[i+1] <- ((4*i - 2)*cat[i])/(i + 1)
      }
   }
   cat[numbs + 1]
}

> catalan(1:15)
 [1]       1       2       5      14      42     132     429
 [8]    1430    4862   16796   58786  208012  742900 2674440
[15] 9694845

这是一个小基准,其中 catrvect = Vectorize(catalan_num_recr)

microbenchmark::microbenchmark(catalan(1:100), catvect(1:100))
Unit: microseconds
           expr      min        lq      mean    median       uq
 catalan(1:100)   86.515   98.7565  127.3139  122.7665  141.423
 catvect(1:100) 4764.728 4947.3070 5661.0624 5124.3385 5647.238
       max neval
   276.825   100
 11009.428   100

当然,现在的函数不是递归的