C语言二项式系数递归函数中双递归return语句工作逻辑解析

这行代码是组合数学中帕斯卡恒等式的直接代码实现，递归拆分逻辑可以从数学定义和程序执行两个层面拆解：

递归拆分的数学依据 #

二项式系数C(n, m)的含义是从n个不同元素中选出m个元素的总选法数。

帕斯卡恒等式规定：从n个元素中选m个的所有选法，可按「是否包含某个固定参考元素X」划分为互不重叠的两类，两类的数量之和即为总选法数。

• 若选法必须包含元素X：只需从剩余n-1个元素中再选出m-1个元素凑够m个，对应数量为C(n-1, m-1)
• 若选法必须不包含元素X：需要从排除了X的n-1个元素中直接选出全部m个元素，对应数量为C(n-1, m)
  两个递归调用分别对应这两类选法的计数，相加就得到总选法数，也就是原问题的计算结果。

程序实际执行流程 #

这行代码的递归逻辑，是将规模为n的原问题，拆解为两个规模为n-1的子问题。每个子问题会重复相同的拆分规则，直到触发已定义的三个终止边界返回固定值：

• m == 0返回1
• m == n返回1
• m > n返回0

以计算C(3,2)的完整调用链路为例：

1. 首次调用binomial(3,2)，不满足所有终止条件，进入else分支，需要计算两个子问题的返回值之和：
   • 调用binomial(2,1)：该调用同样不满足终止条件，继续拆分为两个子调用：
     • 调用binomial(1,0)：触发m==0边界，返回1
     • 调用binomial(1,1)：触发m==n边界，返回1
     • 两个子结果相加，binomial(2,1)最终返回2
   • 调用binomial(2,2)：触发m==n边界，直接返回1
2. 两个子问题的结果相加，最终返回2 + 1 = 3，和二项式系数C(3,2)=3的数学计算结果完全一致。

所有递归分支最终都会收敛到固定的边界返回值，不会出现无限递归的情况。 #

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