Задача 7.6. Рекурсивные функции

Написать программу упорядочивания массива методом быстрой сортировки, используя рекурсию.

Пришло время выполнить обещание, данное на третьем семинаре, — показать рекурсивную реализацию методе быстрой сортировки. Если вы не знаете, что такое рекурсивные функции, загляните в Учебник на с. 82. Говоря кратко, рекурсивной называется функция, в которой имеется обращение к ней самой. Освежите в памяти алгоритм быстрой сортировки, который мы рассматривали, решая задачу 3.3. Там. использовалась «процедура разделения», применяемая к фрагменту массива (изначально - ко всему массиву). На каждом шаге образовывались две половинки текущего фрагмента, и к ним снова нужно было применять процедуру разделения. То есть по своей сути алгоритм является рекурсивным, и если не здесь применять рекурсивные функции, то где?..

К счастью, любая функция в программе на C++ может вызываться рекурсивно. При этом в стеке выделяется новый участок памяти для размещения копий параметров, а также автоматических и регистровых переменных, поэтому предыдущее состояние выполняемой функции сохраняется, и к нему впоследствии можно вернуться (так и произойдет, если только ваша программа где-нибудь не зависнет).

Одна из возможных версий программы сортировки приведена ниже.

Мы не будем подробно анализировать эту программу, поскольку алгоритм вам знаком по задаче 3.3. Отметим только, что процедура разделения реализована здесь в виде рекурсивно вызываемой функции qsort(), в теле которой есть два обращения к самой себе: в операторе 2 — для сортировки левой половинки текущего фрагмента, и в операторе 3 - для сортировки его правой половинки. Надеемся, что сравнение этой программы с предыдущей нерекурсивной версией (задача 3.3) вызовет у вас истинное эстетическое наслаждение1.

Однако, у рекурсии есть и недостатки: во-первых, такую программу труднее отлаживать, поскольку требуется контролировать глубину рекурсивного обращения, вo-вторых, при большой глубине стек может переполниться, а в-третьих, использование рекурсии повышает накладные расходы (например, в данном случае в стеке сохраняются отнюдь не два числа, представляющие собой границы фрагмента, а гораздо больше, не говоря уже о затратах, связанных с вызовом функции). Поэтому рекурсию при всей ее красоте следует применять с осторожностью.