Enter number to find: 6

Processing Processing Processing Processing Processing Processing Processing Processing Processing Processing Processing Processing Processing Processing Processing 8 is the 6

fib(6). fib(4). fib(2). fib(3). fib(l), fib(2). fib(5). fib(3). fib(1). fib(2). fib(4). fib(2). fib(3). fib(l). fib(2). th Fibonac

Call fib(4) Call fib(2) Return 1! Call fib(l) Return 1! Return 1! Call fib(3) Call fib(1) Return 1! Return 1! Call fib(2) Return 11 Call fib(1) Return 1! Return 1! ci number

and fib(5). and fib(3).

and fib(2).

and fib(4). and fib(2).

and fib(3). and fib(2).

примечание

Некоторые компиляторы испытывают затруднения с использованием операторов в выражениях с объектом cout. Если вы получите предупреждение в строке 28, заключите операцию вычитания в круглые скобки, чтобы строка 28 приняла следующий вид:

cout Call fib( (n-2) ) and fib( n-1 ).\ n ;

В строке 9 профамма предлагает ввести номер искомого члена ряда и присваивает его переменной п. Затем вызывается функция fib() с аргументом п. Выполнение профаммы переходит к функции fib(), где в строке 20 этот аргумент выводится на экран.

В сфоке 21 проверяется, не меньше ли аргумент числа 3, и, если это так, функция fib() возвращает значение 1. В противном случае выводится сумма значений, возвращаемых при вызове функции fib() с аргументами п-2 и п-1. Таким образом, эту программу можно представить как циклический вызов функции fib(), повторяющийся до тех пор, пока при очередном вызове этой функции не будет возвращено некоторое значение. Единственными вызовами, которые немедленно возвращают значения, являются вызовы функций fib(l) и fib(2). Рекурсивное использование функции fib() проиллюстрировано на рис. 5.4 и 5.5.

В примере, изображенном на рисунках, переменная п равна значению 5, поэтому из функции mainO вызывается функция fib(6). Выполнение программы переходит в тело функции fib(), и в строке 30 значение переданного аргумента сравнивается с числом 3. Поскольку число 5 больше числа 3, функция fib(6) возвращает сумму значений, возвращаемых функциями fib(4) и fib(5):

38: return( fib(n-2) + fib(n-l));

Это означает, что выполняется обращение к функциям fib(4) и fib(5) (поскольку переменная п равна числу 6, то fib(n-2) - это то же самое, что fib(4), а fib(n-l) - то же самое, что fib(5)). После этого функция fib(6), которой в текущий момент пере-

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

int mainO (

intx = Rb(6)

fib(6)

fib(5)

return 1 J I return 1 J j return 1 j return 1 j j return 1 j

Puc. 5.4. Использование рекурсии

Рис. 5.5. Возвращение из рекурсии

Поскольку при вызове функции fib(5) передается аргумент, который не меньше числа 3, функция fib() будет вызываться снова, на этот раз с аргументами 4 и 3. А функция flb(4) вызовет, в свою очередь, функции flb(3) и fib(2),

Результаты и промежуточные этапы работы профаммы, представленной а листинге 5.10, выводятся на экран. Скомпилируйте, скомпонуйте и выполните эту программу, введя сначала число 1, затем 2, 3, и так доберитесь до числа 6, внимательно наблюдая за отображаемой информацией.

Работа с этой профаммой предоставляет вам прекрасный шанс проверить возможности своего отладчика. Разместите точку останова в сфОке 20, а затем заходите в тело каждой вызываемой функции fib(), отслеживая значение переменной п при каждом рекурсивном вызове функции fib().

В профаммировании на языке С++ рекурсия не частый гость, но в определенных случаях она является мощным и весьма элегантным инструментом.

примечание

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

Работа функции - приподнимем завесу тайны

При вызове функции управление профаммой передается вызванной функции. Происходит передача параметров, после чего начинается выполнение операторов, составляющих тело функции. По завершении выполнения функции возвращается некоторое значение (если не определено, что функция возвращает тип void) и управление передается вызывающей функции.

Как же реализуется эта задача? Откуда профамме известно, к какому блоку ей сейчас нужно перейти? Где хранятся переменные при передаче их в качестве аргументов? Что происходит с переменными, которые объявляются в теле функции? Как передается назад возвращаемое значение? Откуда профамме известно, с какого места ей нужно продолжить работу?

Многие авторы даже не делают попыток ответить на все эти вопросы, но без понимания принципов работы функций программирование вам покажется сплошным шаманством. Объяснение же потребует краткого освещения вопросов, связанных с памятью компьютера.

Уровни абстракции

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

Некоторых программистов пугает любой уровень детализации, опускающийся ниже понятий о значениях, хранящихся в ОЗУ. В конце концов, вам не нужно понимать физику элементарных частиц, чтобы управлять автомобилем, печь пироги или бить по мячу. Точно так же, чтобы программировать, можно обойтись без понимания электроники компьютера.