我的k子数组乘积问题解决方案为何失效且出现段错误？

我实现了一个利用XOR判断乘积是否已计算过的解决方案，通过递归获取所有可能的乘积，代码如下：

#include <stdio.h>
int driver(int *arr, int k, int n){
    int counter=0;
    int sbc=0;
    while(counter++<n){
        d_recursive(arr,k,n,1,0,arr[counter],&sbc);
    }
    return sbc;
}
void d_recursive(int *arr, int k, int n, int p, int prvc, int currc, int *sbc){
    int counter=0;
    while(counter++<n){
        if(currc^arr[counter]*p!=prvc&&arr[counter]*p<k){
            *sbc++;
            d_recursive(arr,k,n,arr[counter]*p,currc,currc^arr[counter]*p,sbc);
        }
    }
}
int main(int argc, char **argv){
    if(argc<3){
        printf("Usage: %s [array of numbers] [value of k]\n",argv[0]);
        return 1;
    }
    puts("Converting string arguments to integers(and adding them to a set).");
    int i_arr[argc-2];
    int prev_cache=0;
    int curr_cache=atoi(argv[1]);
    int counter=2;
    while(counter++<argc-1){
        if(curr_cache^atoi(argv[counter])!=prev_cache){
            i_arr[counter]=atoi(argv[counter]);
            prev_cache=curr_cache;
            curr_cache^=i_arr[counter];
        }
    }
    puts("Finished conversion.");
    puts("Passing values to function.");
    int output=driver(i_arr,atoi(argv[argc-1]),argc-2);
    printf("Finished. Output is %d.",output);
    return 0;
}

我尝试每次调用d_recursive时打印字符，发现调用次数极多，奇怪的是输入数组大小为3和7时，出现段错误的时间相同，请问这是为什么？

问题原因分析 #

1. 无效的XOR去重逻辑导致无限递归

你想用XOR判断乘积是否已计算的思路完全错误：

• XOR是按位异或运算，无法唯一标识已出现的乘积：不同的乘积可能得到相同的异或结果，相同的乘积在不同异或顺序下也会得到不同结果，根本无法准确去重。
• 当前的条件currc^arr[counter]*p!=prvc完全起不到过滤重复乘积的作用，只要arr[counter]*p < k成立，就会不断触发递归调用，形成无限递归。

2. 栈溢出速度与数组大小无关

段错误的本质是递归调用耗尽了栈空间。不管数组大小是3还是7，只要数组中存在能让乘积持续小于k的元素（比如元素为1，乘积永远为1，只要k>1就会无限递归），递归调用会以极快的频率压入栈帧，栈空间会在几乎相同的时间内被耗尽，因此段错误出现的时间相近。

3. 代码中的其他致命问题

• 数组越界：main函数中i_arr[counter]的赋值会触发越界——i_arr的大小是argc-2，但counter会遍历到argc-1，超出数组索引范围，导致内存混乱，可能进一步加剧错误。
• 遍历遗漏元素：driver函数的循环counter++<n会跳过数组的第一个元素（arr[0]），初始counter=0，第一次循环后counter=1，直接访问arr[1]，导致部分元素未被处理。
• 递归逻辑错误：递归中传递的p是arr[counter]*p，但没有限制递归深度，也没有正确的终止条件，一旦进入递归就无法退出。

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