Несколько вызовов оператора рекурсии

Question

void quickSort(int *a, int beg, int end)
{                       
  int pivotLoc;

  if (beg < end)
  {         
    partitionArray(a, beg, end, &pivotLoc);       
    quickSort(a, beg, pivotLoc - 1); 
    quickSort(a, pivotLoc + 1, end);
  } 
}

Когда вызывается 2-й оператор рекурсии?

Когда завершается 1-й оператор рекурсии?

У меня большая путаница во многих вызовах операторов рекурсии.

Не могли бы вы уточнить это?

Answer 1

Вопрос можно обобщить:

void f()
{
    f() // 0
    f() // 1
    // ...
    f() // n
}

Если мы рисуем граф вызовов из, мы (конечно) получаем древовидную структуру:

               f()
        /     /      \
    /(0)    /(1)  ....  \(n)
f()       f()               f()

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

Теперь, если у нас есть два произвольных вызова функции f(); g();, следующих друг за другом, g может быть вызван только когда f() возвращается.Это, конечно, относится и к двум последующим рекурсивным вызовам, что, в свою очередь, подразумевает, что дерево вызовов обязательно обходит, как при поиске в глубину.

Возвращаясь к вашему примеру быстрой сортировки (и игнорируя дляпростота в том, что разделение не должно приводить к двум половинкам одинакового размера), тогда вторая половина каждого подмассива будет отсортирована только после завершения предыдущей половины.Рассматривается глобально:

sort first half
  sort first quarter
    sort first eighth
    sort second eighth
  sort second quarter
    sort third eighth
    sort fourth eighth
sort second half
  sort third quarter
      // ...
  sort fourth quarter
      // ...

Answer 2

Давайте рассмотрим небольшой пример, чтобы понять рекурсию сейчас.

Допустим, вы вызываете quickSort для следующего массива как:

int a = {3,1,4,2,5};
quickSort(a,0,4);

Теперь давайте начнем трассировку.

1. Сначала вам позвонят на quickSort(a,0,4).
2. Затем этот вызов объявляет локальную переменную pivotLoc.
3. Затем вы проверяете условие beg<end, где beg = 0 и end = 4 (как вы передали их на шаге 1).
4. Теперь вы вызываете функцию с именем partitionArray(a,0,4,address_of_pivotLoc);
5. При возврате функции partitionArray было установлено значение переменной pivotLoc.
6. Теперь вы вызываете quickSort(a, 0, pivotLoc-1), которые снова повторяются с первого шага, КРОМЕ end равно , а не 4, но равно pivotLoc-1.

Когда вызывается 2-й оператор рекурсии?

Ответ: Когда условие beg<end не выполняется в первом рекурсивном вызове, оно просто возвращается.Это время, когда второй рекурсивный вызов начинает выполняться с последнего вызова первой рекурсии (т. Е. С последнего вызова, когда первая рекурсия не не выполнила условие beg<end).

Когда выйдет 1-й оператор рекурсии?

Ответ: Если он не выполнит условие beg<end, он достигнет конца своей функции и вернется кпредыдущий вызов той же функции .Затем начинается второй рекурсивный вызов.

TLDR;В основном условие, которое делает любой из quickSort вызовов, заканчивающихся, является if условием beg<end.