c++ - 如何将给定的代码转换为数学函数？

Question

我正在尝试将递归转换为数学公式。下面的代码片段 (c++) 是一个简化的变体。这些值看起来像指数函数，但我试图找到一个封闭的形式。例如，rec(8, 6) 是 1287。作为一个假设，我首先假设 6 是常数，并尝试找到 rec(?, 6) 的指数函数>。然而，这些结果极其不准确。有谁知道我如何实现封闭功能？非常感谢

int rec(const int a, const int b, const int c = 0, const int d = 0)
{
  int result = 0;
  if (d == a)
    ++result;
  else
    for (int i = 0; c + i < b; ++i)
      result += rec(a, b, c + i, d + 1);
  return result;
}

Answer 1

不存在将递归函数转换为数学封闭函数的通用方法。在你的情况下，答案是 the number of "b-1" combinations from an "a"-element set ，即 a!/((a-b+1)!(b-1)!)。

证明:您的rec相当于

int rec(const int a, const int b)
{
  if (0 == a)
    return 1;

  int result = 0;      
  for (int i = 0; i < b; ++i)
      result += rec(a - 1, b - i);
  return result;
}

因为最重要的是 a-d 和 b-c。

如果 a==0，rec 返回 1

如果 a>0，则返回 rec(a-1, i) 的总和，其中 i 位于 (0, b) 中。这是正确的，并且仅适用于组合。如果你让我证明这一点，我会的，但是纯文本格式不适合数学证明

编辑:一般想法:将所有rec(i,j)打印为表格，并尝试通过查看表格来发现规则。我做了:

for (int i = 0; i != 10 ; ++i){
  for (int j = 0; j != 10; ++j){
    cout << rec(i, j) << "\t";
  }
  cout << endl;
}

这样我发现它是 Pascals_triangle