Освой самостоятельно С++ за 21 день.
Шрифт:
Предупреждение: При запуске программы, представленной в листинге 6.10, задавайте небольшие номера членов ряда Фибоначчи (меньше 15). Поскольку в этой программе используется рекурсия, возможны большие затраты памяти.
Листинг 5.10. Пример использования рекурсии для нахождения члена ряда Фибоначчи
1: #include <iostream.h>
2:
3: int fib (int n);
4:
5: int main
6: {
7:
8: int n, answer;
9: cout << "Enter number to find: "; 10: cin >> n;
10:
11: cout << "\n\n";
12:
13: answer = fib(n);
14:
15: cout << answer << " is the " << n << "th Fibonacci number\n"; 17: return 0,
16: }
17:
18: int fib (int n)
19: {
20: cout << "Processing fib(" << n << ")... "; 23:
21: if (n < 3 )
22: {
23: cout << "Return 1!\n";
24: return (1);
25: }
26: else
27: {
28: cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
29: return( fib(n-2) + fib(n-l));
30: }
31: }
Результат:
Enter number lo find: 6
Processing fib(6)... Call fib(4) and fib{S)
Processing fib(4)... Call fit>(2) and fib(3)
Processing fib(2)... Return 1!
Processing fib(3)... Call fib(l) and fiO<2)
Processing fib(D... Return 1!
Processi ng fib(2)... Return 1!
Processing fib(5)... Call fib(3) and fib{4)
Processing fib(3}... Call fib(1) and fib(2)
Processing flb(1)... Return 1!
Processi ng fib(2)... Return 1!
Processing fib(4)... Call fib(2) and fib(3)
Processing fib(2)... Return 1!
Processing fib(3)... Call fib(1) and fib(2)
Processing fib(l)... Return 1!
Processing fib(2)... Return 1!
8 is the 6th Fibonacci number
Примечание:Некоторые
28: cout << "Call fib(" << (n-2) << ") and fib(" << n-1 << ").\n";
Анализ: В строке 9 программа предлагает ввести номер искомого члена ряда и присваивает его переменной n. Затем вызывается функция fib с аргументом n. Выполнение программы переходит к функции fib, где в строке 20 этот аргумент выводится на экран.
В строке 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),
Рис. 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) и управление передается вызывающей функции.
Как же реализуется эта задача? Откуда программе известно, к какому блоку ей сейчас нужно перейти? Где хранятся переменные при передаче их в качестве аргументов? Что происходит с переменными, которые объявляются в теле функции? Как передается назад возвращаемое значение? Откуда программе известно, с какого места ей нужно продолжить работу?
Многие авторы даже не делают попыток ответить на все эти вопросы, но без понимания принципов работы функций программирование вам покажется сплошным шаманством. Объяснение же потребует краткого освещения вопросов, связанных с памятью компьютера.
Уровни абстракции
Одно из основных препятствий для начинающих программистов — преодоление нескольких уровней абстрагирования от реальности. Компьютеры, конечно, всего лишь электронные машины. Они ничего не знают об окнах и меню, о программах или командах, они даже ничего не знают о единицах и нулях. Все, что происходит в действительности, связано лишь с измерением напряжения в различных точках интегральных микросхем. И даже это является абстракцией. Само электричество представляет собой лишь умозрительную концепция, обобщающую поведение элементарных частиц.