求解n个对象拆分为最大m尺寸部分的分割数Java递归代码排错

你的递归逻辑存在无限递归bug，错误出在递推式的第二个分支：
整数拆分（将n拆为若干不超过m的正整数之和，不计顺序）的递推关系基于两个互斥的独立场景：

• 拆分方案中至少包含一个大小为m的部分：此时剩下的n-m仍然可以用不超过m的部分拆分，对应你写的part(n-m, m)，这部分逻辑正确。
• 拆分方案中完全不包含大小为m的部分：此时相当于把n拆为不超过m-1的部分之和，你错误地把这个分支写成了part(n, m)，参数没有任何收敛，会无限递归调用自身最终栈溢出，永远无法返回结果。

额外补充一个边界优化逻辑：当m > n时，不可能拆出比总数量n还大的部分，此时等价于part(n, n)，加上这个判断可以减少无效递归调用。

public class Partition {
    public static void main(String[] args) {
        System.out.println(part(6,4));
    }

    public static int part(int n, int m) {
        if (n == 0) {
            return 1;
        }
        if (m == 0 || n < 0) {
            return 0;
        }
        if (m > n) {
            return part(n, n);
        }
        return part(n - m, m) + part(n, m - 1);
    }
}

你用的测试用例part(6,4)正确返回值为9，对应所有合法拆分方式：

• 4+2、4+1+1
• 3+3、3+2+1、3+1+1+1
• 2+2+2、2+2+1+1、2+1+1+1+1
• 1+1+1+1+1+1
  运行修正后的代码可以正确得到该结果，不会出现无限递归的问题。

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