为从 i 到 n 求和的递归方法编程

Question

我正在尝试为以下等式编写递归方法，用于从 i 到 n 求和，其中 f(0)=f(1)=1。

f(n) = from i = 1 to n ∑f(i-1) * f(n-i)

这是我目前所知道的，当 n=4

时出现堆栈溢出错误

Answer 1

您的方法与您提供的方程不匹配。您声明：

n ∑c(i-1)*c(n-i)

但您的最终 return 陈述是：

c(i-n) * c(i-1)

也许你应该试试：

c(n-i) * c(i-1)

当我传入 4 时，它会生成以下调用堆栈：

i = 0, n = 4
  c(i - n) with i = 1

i = 1, n = -3
  c(i - n) with i = 1

i = 1, n = 4
  c(i - n) with i = 2

i = 2, n = -2
  c(i - n) with i = 2

i = 2, n = 4
  c(i - n) with i = 3

i = 3, n = -1
  c(i - n) with i = 3

i = 3, n = 4
  c(i - n) with i = 4 becomes c(0) becomes 1
  c(i - 1) with i = 4

i = 4, n = 3
  c(i - n) with i = 4 becomes c(1) becomes 1
  c(i - 1) with i = 4 becomes c(3) and it repeats from this point on

所以基本上当 i 达到 4 并且您的 n 为 3 时，您最终会调用 c(3)，然后触发调用 c(i - 1) a.k.a。 c(3)一次又一次。

如果您按照我的建议进行更改，则相同的调用会调用：

c(n - i) -> c(4 - 1)
  c(n - i) -> c(3 - 2) -> c(1) -> 1
  c(i - 1) -> c(1) -> 1
c(i - 1) -> c(1) -> 1

在最后一行，i 已变为 2，尽管它位于顶层，因为该变量的共享性质。

Answer 2

对于递归求和，您将得到如下结果：

public int sum(int start, int end)
{
  if(start >= end)
  {
    return end;
  }
  return start +sum(start+1,end);
}

此方案可以适应您要使用的公式：

 static long c(long x)
  {
    if(x <2) return 1;
    return sumC(1,1,x);
  }

  static long sumC(long start,long current,long stop)
  {
      if(current>stop) return 0;
      return c(current-1)*c(stop -current) + sumC(start,current+1,stop);
  }

0 to 10 : 1 1 2 5 14 42 132 429 1430 4862 16796

Answer 3

如果您确实需要使用递归，您的函数将如下所示：

static long catalan(int n) {
    return c(1, n);
}

static long c(int i, int n) {
    if (n <= 1) {
        return 1;
    } else if (i > n) {
        return 0;
    } else {
        return catalan(i - 1) * catalan(n - i) + c(i + 1, n);
    }
}

虽然，正如其他人所说，使用记忆的版本会快得多，但如果您只是为了学习和测试而这样做的话，这会很好。

if (n <= 1) return 1 是您的基本情况。
else if (i > n) return 0是当i大于n时停止求和。
return catalan(i - 1) * catalan(n - i) + c(i + 1, n)是求和，其中i加1，直到达到n。

为从 i 到 n 求和的递归方法编程

Programming a recursive method for summation from i to n

java

algorithm

recursion