Вызов функции рекурсивно более одного раза

Question

Я новичок в программировании. Пожалуйста, объясните мне, как работает нижеприведенная функция рекурсии. Функция вызывается рекурсивно дважды. Будут ли выполнены операторы после 1-го рекурсивного вызова?

void sort(int low, int high) {
   int mid;

   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else { 
      return;
   }   
}
void main()
{
   sort(0, 10);
}

Answer 1

Позволяет идти за строкой

1. Сначала ваша функция сортировки будет запущена для аргументов 0 и 10, это будет первый вызов этой функции.
2. Из строки if(low < high) Поскольку 0 <10, то в середине будет 5: из-за <code>mid = (low + high) / 2;.
3. Теперь снова будет выполняться функция сортировки для аргументов 0 и 5, это будет второй вызов этой функции, но помните, что первый вызов все еще не завершил свою работу.
4. Так как 0 <5, то середина будет 2. </li>
5. Теперь снова функция сортировки будет работать на этот раз для аргументов 0 и 2, это будет третий вызов, а вторая функция останется работать.
6. , поскольку 0 <2 mid будет 1. </li>
7. Теперь снова функция сортировки будет запущена на этот раз для аргументов 0 и 1, это будет четвертый вызов, а третий вызов функции останется работать.
8. , поскольку 0 <1 середина будет 0. </li>
9. Теперь снова функция сортировки будет запущена на этот раз для аргументов 0 и 0, это будет пятый вызов, и четвертый вызов функции будет работать.
10. , поскольку 0 <0 теперь ложно, будет выполнен обратный вызов в else, и эта функция будет уничтожена. Теперь элемент управления вернется к четвертому вызову, который работал для аргументов 0 как низкий и 1 как высокий. </li>
11. Теперь из пятой строки sort(mid+1, high); вашего кода будет вызываться снова на этот раз для low = 1 и high также = 1.
12. Теперь снова будет вызвана функция сортировки, и это шестой вызов, и на этот раз она будет выполняться для аргументов low = 1 и high = 1, и она начнет выполняться с первой строки вашего кода.

Считайте это стеком: сначала нажмите sort(0,10), затем => sort(0,5), затем => sort(0,2), затем => sort(0,1), затем => sort(0,0)

Теперь, когда sort(0,0) завершил выполнение, он будет удален из стека и sort(0,1) продолжится. Так должно выглядеть вот так

sort(0,10) => sort(0,5) => sort(0,2) => sort(0,1)

Снова в пятой строке sort(0,1) есть вызов sort(), поэтому снова сортировка будет помещена в этот стек:

sort(0,10) => sort(0,5) => sort(0,2) => sort(0,1) => sort(1,1)

Это будет продолжаться, и, наконец, вызов к sort(0,10) завершится, и вы получите желаемый результат.

Answer 2

см. Ссылку на пример рекурсии из переполнения стека. Примеры рекурсивных функций

Чего вы пытаетесь достичь в коде? Функция рекурсии должна вызывать саму функцию и должна иметь условие остановки, иначе она будет идти в бесконечном цикле. Код, который вы написали, дважды вызывал одну и ту же функцию, что неверно. Вы должны вызывать функцию один раз и с условием остановки.