如何将给定C++递归代码转换为对应的数学闭式函数？

递归函数的闭式表达式 #

这个递归对应的闭式为组合数：C(a + b - 1, a)（等价于C(a + b - 1, b - 1)，其中C(n, k)代表从n个元素中选k个的组合数）。

推导过程 #

• 首先拆解递归逻辑：你定义的rec(a,b,0,0)本质是在计数满足条件的路径数：一共走a步，每一步选一个非负整数i，要求每一步走完后的累计和小于b，走满a步就算一条有效路径。
• 由于每一步选的i都是非负整数，因此「每一步的累计和都小于b」等价于「a步选的所有i的总和小于b」，也就是总和≤b-1。
• 根据经典的隔板法计数：a个非负整数的和≤k的解的个数就是组合数C(a + k, a)，这里k = b-1，代入后就得到C(a + b - 1, a)。

验证与拟合问题说明 #

• 你给出的测试用例rec(8,6)代入公式得C(8+6-1, 8) = C(13,8) = 1287，和实际返回值完全匹配。
• 你之前拟合指数函数误差极大的原因很简单：当b为固定常量时，C(n + b - 1, b-1)是关于n的b-1次多项式，比如b=6时就是5次多项式，完全不是指数函数，自然拟合误差会非常大。

内容的提问来源于stack exchange，提问作者john