3.12 Рекурсия

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

Сначала мы рассмотрим понятие рекурсии, а затем проанализируем не­сколько программ, содержащих рекурсивные функции. Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи — так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто воз­вращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой — это называетсярекурсивным вызовом, или шагомрекурсии. Шаг рекурсии вклю­чает ключевое слово return, так как в дальнейшем его результат будет объ­единен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова, возможно, в main.

Шаг рекурсии выполняется до тех пор, пока исходное обращение к функ­ции не закрыто, т.е. пока еще не закончено выполнение функции. Шаг ре­курсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части. Чтобы завершить процесс рекурсии, каждый раз, как функции вы­зывает саму себя с несколько упрощенной версией исходной задачи, должна формироваться последовательность все меньших и меньших задач, в конце концов сходящаяся к базовой задаче. В этот момент функция распознает базовую задачу, возвращает результат предыдущей копии функции и после­довательность возвратов повторяет весь путь назад, пока не дойдет до пер­воначального вызова и не возвратит конечный результат в функцию main. Все это звучит довольно экзотично по сравнению с традиционным решением задач, которое мы рассматривали до сих пор. Как пример работы данной концепции, рассмотрим рекурсивную программу для выполнения одного рас­пространенного математического расчета.

Факториал неотрицательного целого числа n, записываемый как n!, равен

nx(n-l)x(n-2)x.. .xl

причем считается, что 1! = 1 и 0! = 1. Например, 51 вычисляется как 5x4x3x2x1 и равен 120

206