Scala 中的加泰罗尼亚数字递归

Question

我知道如何计算 java 中的加泰罗尼亚数字，这非常简单：

int catalan(int n) {
    int res = 0;

    // Base case
    if (n <= 1) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        res += catalan(i) * catalan(n - i - 1);
    }
    return res;
}

但我无法想象如何在 Scala 中执行此操作，因为我对它完全陌生。是否可以在不使用 var 的情况下执行此操作？

我尝试了以下方法，但它不起作用：

object Catalan {

  def catalan: Int => Int = n => {
    val res = 0
    val i = 0

    if (n <= 1) 1 
    else for (i <- 0 to n-1) res += catalan(i) * catalan(n - i - 1)
  }

}

提前致谢:)

Answer 1

这个怎么样？

def catalan(n: Int): Int = 
  if (n <= 1) 1 
  else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum

这里我做的和您的 java-实现一样，但我使用范围（0 到 n）代替 var，并使用它来创建总和。

实施性能可以从记忆中受益匪浅。

Answer 2

我正在使用 fold 而不是 res += 部分，其余逻辑与您的 java 算法相同：

def catalan(n: Int): Int = {
      if (n <= 1) 1
      else (0 until n).fold(0)((acc, i) => acc + catalan(i) * catalan(n - i - 1))
}

Scala 中的加泰罗尼亚数字递归

Catalan Number recursive in Scala

java

recursion

scala

numbers

recursive-datastructures