double arrow

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

Причем же здесь программирование? Оказывается, процедуры и функции в современных

языках программирования также могут вызывать сами себя.

Рекурсивными называются процедуры и функции, которые вызывают сами себя.

Например, функцию вычисления факториала можно записать так:

Int Factorial (int n)

{

if (n <= 0) return 1; // вернуть 1

else return n*Factorial(n-1); // рекурсивныйвызов

}

Обратите внимание, что функция Factorial вызывает сама себя, если n > 0. Для решения

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

void Factorial (int n, int &fact)

{

if (n == 0) fact = 1; // рекурсия закончилась

else {

Factorial(n-1, fact); // рекурсивный вызов, считаем (n-1)!

fact *= n; // n! = n*(n-1)!

}

}

В отличие от функции, процедура может (если надо) возвращать несколько значений-

результатов с помощью параметров, передаваемых по ссылке.

Косвенная рекурсия

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

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

Не допустим бесконечную рекурсию!

При использовании рекурсивных процедур и функций велика опасность, что вложенные

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

Для функции вычисления факториала таким условием является n <= 0. Докажем, что рекурсия в примере, рассмотренном выше, закончится.

1. Рекурсивные вызовы заканчиваются, когда n становится равно нулю.

2. При каждом новом рекурсивном вызове значение n уменьшается на 1 (это следует из того,что вызывается Factorial(n-1,...)).

3. Поэтому, если в начале n > 0, то, постепенно уменьшаясь, n достигает значения 0 и рекурсия заканчивается.

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


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: