Рекурсивные функции

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

Некоторые проблемы легче всего решаются именно с помощью рекурсий. Так рекурсия полезна в тех случаях, когда выполняется определенная процедура над данными, а затем эта же процедура выполняется над результатом. Оба типа рекурсии (прямая и косвенная) выступают в двух амплуа: одни в конечном счете заканчиваются и генерируют возврат, а другие никогда не заканчиваются и генерируют ошибку времени выполнения. Программисты считают, что последний вариант весьма забавен (конечно же, когда он случается с кем-то другим).

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

Чтобы показать пример решения проблемы с помощью рекурсии, рассмотрим ряд Фибоначчи:

1,1,2,3,5,8,13,21,34…

Каждое число ряда (после второго) представляет собой сумму двух стоящих впереди чисел. Задача может состоять в том, чтобы, например, определить 12-й член ряда Фибоначчи.

Один из способов решения этой проблемы лежит в тщательном анализе этого ряда. Первые два числа равны 1. Каждое последующее число равно сумме двух предыдущих. Таким образом, семнадцатое число равно сумме шестнадцатого и пятнадцатого. В общем случае n-е число равно сумме (n-2)-го и (n-1)-го при условии, если n>2.

Для рекурсивных функций необходимо задать условие прекращения рекурсии. Обязательно должно произойти нечто, способное заставить программу остановить рекурсию, или же она никогда не закончится. В ряду Фибоначчи условием останова является выражение n<3.

При этом используются следующий алгоритм:

  1. Предлагаем пользователю указать, какой член в ряду Фибоначчи следует рассчитать.
  2. Вызываем функцию fib( ), передавая в качестве аргумента порядковый номер члена ряда Фибоначчи, заданным пользователем.
  3. В функции fib( ) выполняется анализ аргумента (n). Если n<3,функция возвращает значение 1; в противном случае функция fib( ) вызывает саму себя (рекурсивно), передавая в качестве аргумента значение n-2, затем снова вызывает саму себя, передавая в качестве аргумента значение n-1, а после этого возвращает сумму.

Если вызвать функцию fib(1), она возвратит 1. Если взывать fib(2), она также возвратит 1. Если вызвать функцию fib(3), она возвратит сумму значений, возвращаемых функциями fib(2) и fib(1). Поскольку вызов функции fib(2) возвращает значение 1 и вызов функции fib(1) возвращает значение 1, то функция fib(3) возвратит значение 2.

Если вызвать функцию fib(4), она возвратит сумму значений, возвращаемых функциями fib(3) и fib(2). Мы уже установили, что функция fib(3) возвращает значение 2 (путем вызова функций fib(2) и fib(1)) и что функция fib(2) возвращает значение 1, поэтому функция fib(4) просуммирует эти числа и возвратит значение 3, которое будет являться четвертым членом ряда Фибоначчи.

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

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

Код программы

Анализ

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

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

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

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), которой в текущий момент передано управление программой, ожидает, пока сделанные вызовы не возвратят какое-нибудь значение. Дождавшись возврата значений, эта функция возвратит результат суммирования этих двух значений.

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

Результаты и промежуточные этапы работы программы:

Результат програмы

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

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


далее