В строке 21 проверяется, не меньше ли аргумент числа 3, и, если это так, функция fib() возвращает значение 1. В противном случае выводится сумма значений, возвращаемых при вызове функции fib() с аргументами n-2 и п-1. Таким образом, эту программу можно представить как циклический вызов функции fib(), повторяющийся до тех пор, пока при очередном вызове этой функции не будет возвращено некоторое значение. Единственными вызовами, которые немедленно возвращают значения, являются вызовы функций fib(1) и fib(2). Рекурсивное использование функции fib() проиллюстрировано на рис. 5.4 и 5.5.
В примере, изображенном на рисунках, переменная n равна значению 6, поэтому из функции main() вызывается функция fib(6). Выполнение программы переходит в тело функции fib(), и в строке 30 значение переданного аргумента сравнивается с числом 3. Поскольку число 6 больше числа 3, функция fib(6) возврашает сумму значений, возвращаемых функциями fib(4) и fib(5):
38: return( fib(n-2) + fib(n-1));
Это означает, что выполняется обращение к функциям fib(4) и fib(5) (поскольку переменная n равначислу 6, то fib(n-2) — это то же самое, что fib(4), а fib(n-1) — то же самое, что fib(5)). После этого функция fib(6), которой в текущий момент передано управление программой, ожидает, пока сделанные вызовы не возвратят какое-нибудь значение. Дождавшись возврата значений, эта функция возвратит результат суммирования этих двух значений.
Рис. 5.4. Использование рекурсии
Рис. 5.5. Возвращение из рекурсии
Поскольку при вызове функции fib(5) передается аргумент, который не меньше числа 3, функция fib() будет вызываться снова, на этот раз с аргументами 4 и 3. А функция flb(4) вызовет, в свою очередь, функции fib(3) и fib(2).
Результаты и промежуточные этапы работы программы, представленной в листинге 5.10, выводятся на экран. Скомпилируйте, скомпонуйте и выполните эту программу, введя сначала число 1, затем 2, 3, и так доберитесь до числа 6, внимательно наблюдая за отображаемой информацией.
Работа с этой программой предоставляет вам прекрасный шанс проверить возможности своего отладчика. Разместите точку останова в строке 20, а затем заходите в тело каждой вызываемой функции fib(), отслеживая значение переменной n при каждом рекурсивном вызове функции fib().
В программировании на языке C++ рекурсия не частый гость, но в определенных случаях она является мощным и весьма элегантным инструментом.
Примечание:Рекурсия относится к одной из самых сложных тем программирования. Данный раздел полезен для понимания основных идей ее реализации, однако не следует слишком расстраиваться, если вам не до конца ясны все детали работы рекурсии.
Работа функций - приподнимаем завесу тайны
При вызове функции управление программой передается вызванной функции. Происходит передача параметров, после чего начинается выполнение операторов, составляющих тело функции. По завершении выполнения функции возвращается некоторое значение (если не определено, что функция возвращает тип void) и управление передается вызывающей функции.
Как же реализуется эта задача? Откуда программе известно, к какому блоку ей сейчас нужно перейти? Где хранятся переменные при передаче их в качестве аргументов? Что происходит с переменными, которые объявляются в теле функции? Как передается назад возвращаемое значение? Откуда программе известно, с какого места ей нужно продолжить работу?
Многие авторы даже не делают попыток ответить на все эти вопросы, но без понимания принципов работы функций программирование вам покажется сплошным шаманством. Объяснение же потребует краткого освещения вопросов, связанных с памятью компьютера.
Уровни абстракции
Одно из основных препятствий для начинающих программистов — преодоление нескольких уровней абстрагирования от реальности. Компьютеры, конечно, всего лишь электронные машины. Они ничего не знают об окнах и меню, о программах или командах, они даже ничего не знают о единицах и нулях. Все, что происходит в действительности, связано лишь с измерением напряжения в различных точках интегральных микросхем. И даже это является абстракцией. Само электричество представляет собой лишь умозрительную концепция, обобщающую поведение элементарных частиц.
Некоторых программистов пугает любой уровень детализации, опускающийся ниже понятий о значениях, хранящихся в ОЗУ. В конце концов, вам не нужно понимать физику элементарных частиц, чтобы управлять автомобилем, печь пироги или бить по мячу. Точно так же, чтобы программировать, можно обойтись без понимания электроники компьютера.
Однако вы должны понимать, как в компьютере организована память. Без четкого представления о том, где располагаются ваши переменные после их создания и как передаются значения между функциями, программирование останется для вас непостижимой тайной.
Разбиение памяти
Когда вы начинаете работу со своей программой, операционная система (например, DOS или Microsoft Windows) выделяет различные области памяти в ответ на требования компилятора. Как программисту на C++, вам часто придется интересоваться пространством глобальных имен, свободной памятью, регистрами, памятью сегментов программы и стеками.
Глобальные переменные хранятся в пространстве глобальных имен. Подробнее о пространстве глобальных имен и свободной памяти речь пойдет на следующих уроках, а пока сосредоточимся на регистрах, оперативной памяти и стеках.
Регистры представляют собой специальную область памяти, встроенную прямо в центральное процессорное устройство, или центральный процессор (Central Processing Unit — CPU). На их плечи возложена забота о выполнении внутренних вспомогательных функций, описание большей части которых выходит за рамки этой книги. Но мы все-таки остановимся на рассмотрении набора регистров, ответственных за указание на следующую строку программы в любой момент времени. Назовем эти регистры (все вместе) указателями команд. Именно на указатель команды ложится ответственность следить за тем, какая строка программы должна выполняться следующей.
Сама программа находится в памяти компьютера, которая специально отведена для того, чтобы хранить операторы программы в двоичном формате. Каждая строка исходного текста программы транслируется в ряд команд, а каждая из этих команд хранится в памяти по своему адресу. Указатель команды содержит адрес следующей команды, предназначенной для выполнения. Эта идея иллюстрируется на рис. 5.6.
Рис. 5.6. Указатель команды
Стек — это специальная область памяти, выделенная для хранения данных вашей программы, требуемых каждой вызываемой функцией. Она называется стеком потому, что представляет собой очередь типа "последним пришел — первым вышел" и напоминает стопку тарелок в руках официанта (рис. 5.7).
Принцип "последним пришел — первым вышел" означает, что элемент, добавленный в стек последним, будет вынут из него первым. Большинство же очередей функционирует подобно очереди в театр: первый, кто занял очередь, первым из нее и выйдет (и войдет в театр). Стек скорее напоминает стопку монет, удерживаемых специальным приспособлением. Если расположить в нем 10 монет достоинством в 1 копейку, а затем попытаться вынуть несколько монет, то первой вы достанете ту, что была вставлена последней.
При помещении данных в стек он расширяется, а при возвращении данных из стека — сужается. Невозможно из стопки достать одну тарелку, не вынув предварительно все тарелки, помещенные в стопку перед ней. То же справедливо для данных в стеке памяти.
Рис. 5.7. Стек
Аналогия со стопкой тарелок приводится чаще всего. Такое сравнение довольно наглядно, но не вполне верно в смысле техники выполнения. Более точное представление позволит создать ряд прямоугольных полей, выровненных сверху вниз. Вершиной стека будет служить любое поле, на которое указывает в данный момент указатель вершины стека (эту роль выполняет другой регистр).
Все поля имеют последовательные адреса, и один из этих адресов хранится в регистре указателя вершины стека. Все, что находится ниже вершины стека, относится к стеку. Все, что находится выше вершины стека, игнорируется, как показано на рис. 5.8.
Рис. 5.8. Указатель вершины стека
При помещении некоторого значения в стек оно размещается в поле, расположенном над вершиной стека, после чего указатель вершины изменяется таким образом, чтобы указывать на новое значение. При удалении значения из стека в действительности происходит лишь изменение адреса указателя вершины стека таким образом, чтобы он указывал на подлежащий удалению элемент стека. Принцип действия схематически показан на рис. 5.9.
