стек ошибка переполнения в C++

Question

У меня есть эта функция, которая делает рекурсивный выбора рода для массива:

void SelectionSort::RecursiveSort(int ar[] , int flag, int first, int last){ 
    // first - index of first element and last - index of last element 
    if (flag == 1) 
    { 
     if (first < last)    //ascending 
     { 
      for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]); 

      RecursiveSort(ar, flag, first + 1, last); 
     } 
     if (first == last) return; 

    } 
    else 
    { 
     if (first < last)     //desc 
     { 
      for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]); 

      RecursiveSort(ar,flag, (first + 1), last); 
     } 
     if (first == last) return; 

    } 
} 

Он отлично работает, если размер массива 3000, но я должен сделать эту работу размером> 5000 и его сбой при переполнении стека.

Я искал много потоков, и все они говорят использовать векторы, и у меня есть. Это проблема присваивания, поэтому я должен выполнять сортировку рекурсии как для массивов, так и для векторов. Он работает для векторов, но не для массивов. Также я не должен использовать указатели в этом задании.

Answer 1

Вы можете попробовать использовать хвостовую рекурсию, поэтому компилятор будет оптимизировать его в качестве петли для Вас:

void AscRecursiveSort(int ar[], int first, int last) { 
    if (first >= last) return; 
    for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]); 
    AscRecursiveSort(ar, first + 1, last); 

} 

void DescRecursiveSort(int ar[], int first, int last) { 
    if (first >= last) return; 
    for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]); 
    DescRecursiveSort(ar, first + 1, last); 
} 

void RecursiveSort(int ar[], int flag, int first, int last) { 
    // first - index of first element and last - index of last element 
    if (flag == 1) 
     AscRecursiveSort(ar, first, last);    //ascending 
    else 
     DescRecursiveSort(ar, first, last); 
} 

Answer 2

Если ваш компилятор не оптимизирует хвостовую рекурсию, что решение не будет работать, и вам нужно будет переписать как цикл while, который проверяет базовый регистр. Не публиковать полное решение, потому что это выглядит как домашнее задание.