Песни о Паскале

      { Индексы «делают шаг» навстречу друг другу }
      L:=L+1; R:=R-1;
      end;
      until L > R; { пока индексы не "встретятся" }
      { если левая часть не отсортирована, то сортируем её }
      if R > aL then QuickSort(arg, aL, R);
      { если правая часть не отсортирована, то её тоже сортируем }
      if L < aR then QuickSort(arg, L, aR);
      { выход после сортировки обеих частей }
end;
      { Процедура распечатки массива, arg – строка сообщения }
procedure ShowArray(const arg: string);
var i: integer;
begin
      Writeln(arg);
      for i:=1 to CSize do Writeln(Arr[i]);
      Readln;
end;
var i: integer;
begin       {--- Главная программа ---}
      { Заполняем массив случайными числами }
      for i:=1 to CSize do Arr[i]:=1+Random(1000);
      ShowArray('До сортировки:');
      QuickSort(Arr, 1, CSize);
      ShowArray('После сортировки:');
end.

Взгляните на параметры процедуры QuickSort. Вместе со ссылкой на массив, в процедуру передаются левая (aL) и правая (aR) границы сортируемой части массива (индексы). В процедуре вычисляется вес среднего арбуза по выбранной нами формуле и организуется поочередное встречное движение левого и правого индексов.

Самое интересное происходит после «встречи» индексов, когда массив разбит на две части. Удивительно, что теперь снова дважды вызывается та же самая процедура QuickSort: сначала для левой части массива, а затем – для правой (эти операторы выделены курсивом). Вспомните, – точно так же поступали и фермеры при сортировке арбузов.

«Так там фермеры, а здесь Паскаль! Позволено ль процедуре вызывать саму себя?» – слышу недоверчивый вопрос. Мы свыклись с тем, что из одной процедуры вызывают другую, из второй, – третью и так далее. Но чтобы саму себя? Это ж змея, глотающая свой хвост! Не оттого ли запутался фермер Лефт?

О рекурсии и стеке

Такой самовызов процедур называют рекурсией. «У попа была собака…» – помните? Это рекурсия, познакомимся с нею ближе (с рекурсией, а не собакой).

Легко заметить, что повторные вызовы процедуры QuickSort выполняются с другими значениями левой и правой границ. Чем глубже вызов, тем уже эти границы. С некоторого момента условия (R > aL) и (L < aR) перестают выполняться, и происходит выход из процедуры, – здесь фермеры возвращаются к несортированным частям массива. Таким образом, при выходе мы снова попадаем в эту же процедуру, но в другое место – следующее за вызовом. Окончательный выход из процедуры в главную программу случится только по завершении сортировки всего массива!

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

Разгадка в том, что при каждом входе в процедуру для её параметров и локальных переменных выделяется новый участок памяти. Теперь это будут уже другие параметры и локальные переменные, но с прежними названиями. Однако предыдущие их значения не теряются, а сохраняются в памяти, называемой стеком (Stack).

Что такое стек и как он работает? Случалось ли вам паковать рюкзак или глубокую сумку? Тогда вы знакомы со стеком. Все, что уложено в рюкзак, будет