C语言中使用递归选择排序的分段错误

Question

我已经写了一个C程序。它应该使用递归选择排序，但对于大输入（10000 或更多）会出现分段错误。调试器说段错误发生在 findim 函数中，但我几乎不可能找出它发生的原因，因为 findmin 函数也是递归的，我无法想象计算机对 10000 个数字的输入进行的所有操作。

如果你想知道 inputType 是什么，它决定了数组中值的顺序。这些值分别表示有序、几乎有序、逆序、随机。

这就是我写的全部程序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DIM_VEC 6
#define MAX_RAND 100

typedef enum {
    ORDINATO, QUASI_ORDINATO, INV_ORDINATO, CASUALE
} inputType;

//Funzione genera_array(…)
int *generaArray(int dimensione, inputType tipo_schema);

void swap(int *a, int *b);

//E2_1: Selection Sort ricorsivo con interi
void selectionSortRec(int A[], int dimA, int start);
int findmin(int A[], int minpos, int start, int dim);



int main() {
    setvbuf(stdout, NULL, _IONBF, 0);
    int ord, dim;
    int *array = NULL;
    int N[DIM_VEC] = {100, 1000, 10000, 100000, 200000, 500000};
    double tempo;
    srand(time(NULL));

    printf("\nScegli l'ordine dell'array "
           "\n0 - ORDINATO, 1 - QUASI_ORDINATO, 2 - INV_ORDINATO, 3 - CASUALE");
    scanf("%d", &ord);
    if(ord < 0 || ord > 3)
        ord = 0;

    printf("\nScegliere la dimensione dell'array ");
    for(int i = 0; i < DIM_VEC; i++) {
        printf("\n%d -- %d", i, N[i]);
    }
    scanf("%d", &dim);
    if(dim < 0 || dim > 5)
        dim = 0;

    array = generaArray(N[dim], ord);

    tempo = clock();
    selectionSortRec(array, N[dim], 0);
    tempo = (clock() - tempo) / CLOCKS_PER_SEC;
    printf("\nTempo impiegato: %lf", tempo);

    free(array);

    return 0;
}

//Funzione genera_array(…)
int *generaArray(int dimensione, inputType tipo_schema) {
    int *a = calloc(dimensione, sizeof(int));
    int j;

    switch (tipo_schema) {
        case ORDINATO:
            for(int i = 0; i < dimensione; i++)
                a[i] = i;
            break;
        case QUASI_ORDINATO:
            for(int i = 0; i < dimensione / 2; i++) {
                a[i] = i;
            }
            for(int i = dimensione /2; i < dimensione; i++) {
                a[i] = rand() % MAX_RAND;
            }
            break;
        case INV_ORDINATO:
            j = dimensione;
            for(int i = 0; i < dimensione; i++) {
                a[i] = j;
                j--;
            }
            break;
        case CASUALE:
            for(int i = 0; i < dimensione; i++) {
                a[i] = rand() % MAX_RAND;
            }
            break;
    }

    return a;

}


//E2_1: Selection Sort ricorsivo con interi
void selectionSortRec(int A[], int dimA, int start) {
    int minIndex;

    if (start >= dimA - 1)
        return;

    minIndex = findmin(A, start, start +1, dimA);


    swap(&A[minIndex], &A[start]);
    selectionSortRec(A, dimA, start+1);
}
int findmin(int A[], int minpos, int start, int dim) {

    if (start == dim)
        return minpos;

    if (A[start] < A[minpos])
        minpos = start;
    return findmin(A, minpos, start + 1, dim);

}

void swap(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

我尝试不使用交换函数并验证数组生成函数是否有效，但它们似乎都可以，因为在较小的输入上它们可以工作，并且我尝试打印数组的所有元素并且它可以，但也许我忘记了一些方面。

Answer 1

您可以尝试更改堆栈大小，看看是否可以进一步进行递归，但正如其他人警告的那样……最终您会在某个时候用完它。

更改堆栈大小示例如下（在 linux mint 20.x、gcc 9.4.0 上）

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <sys/resource.h>

int main (int argc, char **argv)
{
    struct rlimit stackSz;

    if ( 0 == getrlimit(RLIMIT_STACK, &stackSz) )
    {
        fprintf(stderr, "current: rl.rlim_cur == %lu rl.rlim_max == %lu\n", stackSz.rlim_cur, stackSz.rlim_max );

        stackSz.rlim_cur *= 2; // double stack size - for example ....
        setrlimit(RLIMIT_STACK, &stackSz);
        if (0 != setrlimit(RLIMIT_STACK, &stackSz) )
           fprintf(stderr, "ERROR: setrlimit error = %s\n", strerror(errno) );
        else
           fprintf(stderr, "updated: rl.rlim_cur == %lu rl.rlim_max == %lu\n", stackSz.rlim_cur, stackSz.rlim_max );
    }
    else
       fprintf(stderr, "ERROR: getrlimit error = %s\n", strerror(errno) );

    return 0;
}

./rlimit 
current: rl.rlim_cur == 8388608 rl.rlim_max == 18446744073709551615
updated: rl.rlim_cur == 16777216 rl.rlim_max == 18446744073709551615