C语言递归过深触发Segmentation fault 如何保障程序持续运行

问题背景 #

我有一个递归函数，用于校验不同参数组合的有效性，校验通过的组合会被添加到数组中。当组合量较小时程序运行正常，但运行时间较长时就会抛出Segmentation fault错误。我基本可以确定错误是递归深度过高导致的，因为我将第一个参数的逻辑从递归改为for循环后，程序的运行时长明显变长。

原有问题代码 #

int* add_without_overflow(tp_t* parameters, int arr[10], int position, int num_parameters, int *size, int* ptr) {
  if(arr[position] > parameters[position].max){
        if(position != 0){
            arr[position] = parameters[position].min;
            arr[position-1]++;
            add_without_overflow(parameters, arr, position-1, num_parameters, size, ptr);
        }
        else{
            return ptr;
        }
  }
  else{
        if(position == num_parameters-1){
           if((parameters[position].constraint)(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5], arr[6], arr[7], arr[8], arr[9])){
              print_configuration(arr, num_parameters);
              ptr = (int*)realloc(ptr, (((*size) +1)*num_parameters) * sizeof(int));
              for(int i = 0; i < num_parameters; i++){
                ptr[((*size)*num_parameters) + i] = arr[i];
              }
              (*size)++;
           }
           arr[position]++;
           add_without_overflow(parameters, arr, position, num_parameters, size, ptr);
        }
        else{
            if(parameters[position].constraint != 0  && !(parameters[position].constraint)(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5], arr[6], arr[7], arr[8], arr[9])){
               for(int i = position+1; i < num_parameters; i++){
                      arr[i] = parameters[i].min;
               }
               arr[position]++;
               add_without_overflow(parameters, arr, position, num_parameters, size, ptr);
            }
            else{
               add_without_overflow(parameters, arr, position+1, num_parameters, size, ptr);
            }
        }
  }
}


void generate_search_space(tp_t* parameters, int num_parameters,
                           search_space_t* search_space) {
  int arr[10];
  for (int i = 0; i < num_parameters; i++){
        arr[i] = parameters[i].min;   
  }
  int size = 0;
  int *sizepointer = &size;
  int *ptr;
  ptr = (int *)malloc(((0) * num_parameters) * sizeof(int));
  ptr = add_without_overflow(parameters, arr, 0, num_parameters, sizepointer, ptr);
  for(int i = 0; i < num_parameters; i++){
      search_space-> parameters[i] = &parameters[i];
  }
  
  search_space->size = size;
  search_space->num_parameters = num_parameters;
  search_space->values = ptr;
}

测试情况与待解决问题 #

第一轮测试校验256种可能的组合，编译运行都正常。第二轮测试要校验总计128^6种组合（实际不需要全部校验，初始版本代码遍历所有组合要运行数小时，优化后的版本可以一次性排除多组无效组合）。
需要解决的核心问题：怎么避免递归过多导致的程序崩溃？还是说这个场景不适合用递归函数，需要完全重写代码？

问题解决 #

根因分析 #

原有代码的问题并非无法执行到return语句（在特定场景下它是可以到达的），而是它采用单一路径遍历所有配置，所有递归调用都会等待最终函数调用返回结果。小体量测试下该逻辑没有问题，但在大体量测试中会生成数千甚至数百万个等待返回的函数调用，数量过多就会触发Segmentation fault错误。

优化后代码 #

void add_to_search_space(tp_t* parameters, int arr[10], int position, int num_parameters, int *size, int** pptr){
   if(position == num_parameters-1){
          
          while(arr[position] < parameters[position].max+1){
                if((parameters[position].constraint)(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5], arr[6], arr[7], arr[8], arr[9])){
                    print_configuration(arr, num_parameters);
                    *pptr = realloc(*pptr, (((*size) +1)*num_parameters)* sizeof(int));
                    
                    for(int j = 0; j < num_parameters; j++){
                         (*pptr)[(*size*num_parameters) + j] = arr[j];
                    }
                    (*size)++;
                }
                arr[position]++;
          }
   }
   else{
          
          while(arr[position] < parameters[position].max+1){
                if(parameters[position].constraint == 0  || (parameters[position].constraint)(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5], arr[6], arr[7], arr[8], arr[9])){
                    add_to_search_space(parameters, arr, position+1, num_parameters, size, pptr);
                }
                for(int i = position+1; i < num_parameters; i++){
                     arr[i] = parameters[i].min;
                }
                arr[position]++;
          }
   }
}

void generate_search_space(tp_t* parameters, int num_parameters,
                           search_space_t* search_space) {
  int arr[10];
  for (int i = 0; i < num_parameters; i++){
        arr[i] = parameters[i].min;   
  }
  int size = 0;
  int *sizepointer = &size;
  int *ptr;
  ptr = (int *)malloc(((0) * num_parameters) * sizeof(int));
  int **pptr;
  pptr = &ptr;
  add_to_search_space(parameters, arr, 0, num_parameters, sizepointer, pptr);
  for(int i = 0; i < num_parameters; i++){
      search_space-> parameters[i] = &parameters[i];
  }
  
  search_space->size = size;
  search_space->num_parameters = num_parameters;
  search_space->values = *pptr;
}

方案总结 #

不要用递归调用单路径遍历所有可能性，大部分工作可以交给while循环完成。这样就不会生成过多递归调用，导致函数执行完成前就耗尽内存。优化后递归深度最多控制在10层，运行正常。

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