C - Segmentation fault - How to allow for ongoing recursion?

Question

I have a recursive function that tries if different combinations of parameters are valid and if so adds them to an array. When the programm runs for a small amount of combinations it runs fine. If however the programm runs a long time, it will throw an error (segmentation fault). I'm pretty sure that the error lies in the deepness of the recursion, because when I run the first parameter not through the recursion but through a for loop the programm runs for a longer time.

Here is the code I am talking about:

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;
}

My first test (the one that properly compiles checks) for 256 possible combinations. My second test checks an total of 128^6 combinations (also not really as the first instance of my code actually checked every combination and ran for hours, the new version can discard multiple combinations at once).

My question now is how can I keep the programm from failing due to the amount of recursions. Or is working with recursive functions just not working here and I need to rewrite the code completly.

Edit: I have rewritten my code now using only less recursions (at most 10 levels) and it works fine now. The problem with this code is not that it doesn't reaches the return statement (it does under the given scenario not specified here). But it works like a single way through all configurations and keeps every recursion waiting for the final function call that gives the return value. For small tests that was fine but for the big test it leads to thousands if not million of functions waiting for return statements which where so many that I got the segmentation fault error.

This is the better solution:

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;
}

TL;DR: Don't be like me and make a single path through all possibilities using recursive functions calls, when while loops can do most of the work to. That way you don't open so many recursions that you flood your memory before your function finishes.

Answer 1

Any time you have recursion, you run the risk of depleting your stack space if your recursion is too deep. In looking at your code, assuming a 64-bit platform, it looks like you might be using 80 bytes of stack for each level of recursion. The compiler pushes the parameters onto the stack, then makes the call and any local variables that are defined in the function are also push onto the stack. Assuming you are running Linux, the default stack size I believe is 8kb. There are unmapped guard pages before and after the stack region in memory, so an access to one of those will cause the CPU to throw a page fault exception which results in the kernel throwing a segmentation fault for your program.

Best coding practices for recursion is to keep the number of parameters and local variables to a minimum. 80+ bytes of stack frame is huge, and you will run out of stack very quickly. Recursion is great if you are working with trees. In some cases, it's the only solution.

Now, looking at your code, I see a big problem. The first version is missing returns. You are returning a pointer, and if you don't return something, you will get a random value back. When you try to use it, you will get undefined behavior. The best case scenario is a page fault (segmentation fault). However, if the memory address points to a mapped memory page, then the program MAY continue to function but give an unexpected result, or crash in another place, which will make debugging very difficult.

Answer 2

You have many paths in your code that reach the end of the function without returning any value which leads to undefined behavior (as your function is declared as returning a value). You also have recursive calls that discard the returned value, which is suspicious.