Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Рекурсия

В языке С функции разрешено вызывать саму себя. Этот процесс называется рекурсией. Временами рекурсия бывает сложной, но иногда и очень удобной. Сложность связана с доведением рекурсии до конца, т.к. функция, которая вызывает сама себя, имеет тенденцию делать это бесконечно, если в коде не предусмотрена проверка условия завершения рекурсии.

342 Глава 9

Рекурсия часто может применяться там, где используется цикл. Иногда более очевидным является решение с циклом, а иногда — решение с рекурсией. Рекурсивные решения более элегантны, но менее эффективны, чем решения с циклами.

Рекурсия в действии

Давайте взглянем на пример рекурсии. Функция main() в листинге 9.6 вызывает функцию up and down(). Назовем это “первым уровнем рекурсии”. Затем функция up and down() вызывает саму себя; назовем это “вторым уровнем рекурсии”. Второй уровень вызывает третий уровень рекурсии и т.д. В этом примере настроены четыре уровня рекурсии. Чтобы посмотреть, что происходит внутри, программа не только отображает значение переменной n, но также и значение &п, которое представляет собой адрес ячейки памяти, где хранится переменная n. (Операция & более подробно обсуждается позже в главе. Для вывода адресов в printf() применяется спецификатор %р. Если ваша система не поддерживает этот формат, попробуйте воспользоваться спецификатором %u или %lu.)

Листинг 9.6. Программа recur.с

Вывод на одной из систем выглядит следующим образом:

Уровень 1: ячейка n 0x0012ff48 Уровень 2: ячейка n 0x0012ff3c Уровень 3: ячейка n 0x0012ff30 Уровень 4: ячейка n 0x0012ff24 УРОВЕНЬ 4: ячейка n 0x0012ff24 УРОВЕНЬ 3: ячейка n 0x0012ff30 УРОВЕНЬ 2: ячейка n 0x0012ff3c УРОВЕНЬ 1: ячейка n 0x0012ff48

Давайте пройдемся поданной программе, чтобы посмотреть, как работает рекурсия. Сначала main() вызывает up_and_down() с аргументом 1. В результате формальный параметр n функции up_and_down() получает значение 1, поэтому первый оператор вывода отображает строку Уровень 1:. Далее, поскольку n меньше 4, функция up_and_down() (уровень 1) вызывает функцию up_and_down() (уровень 2) с фактическим аргументом n + 1, или 2. Это приводит к тому, что n в вызове уровня 2 присваивается значение 2, так что первый оператор вывода отображает строку Уровень 2 :. Аналогично, следующие два вызова приводят к выводу Уровень 3: и Уровень 4:.

Функции 343

Когда достигнут уровень 4, переменная n равна 4, поэтому проверка в i f не проходит. Функция up and down() не вызывается снова. Вместо этого вызов уровня 4 продолжается выполнением второго оператора вывода, который отображает строку УРОВЕНЬ 4:, т.к. переменная n имеет значение 4. В этой точке вызов уровня 4 заканчивается, а управление возвращается функции, которая его инициировала (вызов уровня 3). Последним оператором, выполненным внутри вызова уровня 3, был вызов уровня 4 в операторе if. Следовательно, выполнение уровня 3 возобновляется со следующего оператора, которым является второй оператор вывода. Это приводит к отображению строки УРОВЕНЬ 3:. Затем уровень 3 завершается, передавая управление уровню 2, который выводит строку УРОВЕНЬ 2 :, и т.д.

Обратите внимание, что на каждом уровне рекурсии применяется собственная закрытая переменная n. Этот факт легко установить, взглянув на значения адресов. (Конечно, в общем случае в разных системах адреса будут отличаться и возможно иметь другие форматы. Важный момент заключается в том, что адрес в строке Уровень 1: совпадает с адресом в строке УРОВЕНЬ 1: и т.д.)

Если вы находите приведенное объяснение слегка запутанным, то представьте, что имеется цепочка вызовов функций, в которой funl() вызывает fun2(), fun2() вызывает fun3() и fun3() вызывает fun4(). Когда fun4() завершается, управление передается fun3(). По завершении fun3() управление передается fun2(). Когда заканчивается fun2(), управление возвращается обратно fun1(). Рекурсивный случай работает точно так же, за исключением того, что функции fun1(), fun2(), fun3() и fun4() являются одной и той же функцией.

основы рекурсии

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

Во-первых, каждый уровень вызова функции имеет собственные переменные. То есть переменная n уровня 1 отличается от переменной n уровня 2, так что программа создает четыре разных переменных, каждая из которых имеет имя n и собственное значение, отличающееся от других. Когда в конечном итоге программа возвращается к вызову функции up and down() первого уровня, исходная переменная n по-прежнему имеет значение 1, с которого она начинала (рис. 9.4).