java - 包含排除原理中递归函数对其自身求和

Question

此代码用于使用包含排除原理来获取可被 2, 3, 5, 7 整除的数字，并且效果很好。

public class Inclusion_Exclusion_Recursion {

private static int inc_exc(int index , int set , int sign){
    int no_of_elements = 100;
    int[] primes = new int[]{2,3,5,7};

    if(index == 4){
        if(set == 1){
            return 0;
        }
        return sign * no_of_elements / set;
    }

    return inc_exc(index+1, set, sign) +
            inc_exc(index+1, set * primes[index], sign * -1);

 };

 public static void main(String args[]){
    System.out.print(inc_exc(0, 1, -1));
 }
}

我将递归理解为一种技术，但我不明白当我们将递归函数求和时，递归是如何工作的。 inc_exc(索引+1，集合，符号) + inc_exc(索引+1，集合 * primes[索引]，符号 * -1);

当我调查时，我发现第一次递归 inc_exc(index+1, set, sign) 每次都会减少索引，索引达到 4 (我不知道也不太明白这一点)。然后第二个递归开始工作 inc_exc(index+1, set * primes[index], sign * -1)，如果我错了，请纠正我。

您能详细解释一下这个递归是如何工作的吗？

Answer 1

如果索引达到 4，则递归停止。如果索引不是 4，则方法调用的结果是两次递归调用的总和:

return inc_exc(index+1, set, sign) +
        inc_exc(index+1, set * primes[index], sign * -1);

现在你的调用堆栈中有两个函数调用，索引为 1。这仍然不是 4，你继续使用索引 2 进行 2 * 2 = 4 次递归调用。最后，你有 2 ^ 4 = 16 个函数调用，索引 4(因为您在主函数中从索引 0 开始)。