Причем же здесь программирование? Оказывается, процедуры и функции в современных
языках программирования также могут вызывать сами себя.
Рекурсивными называются процедуры и функции, которые вызывают сами себя.
Например, функцию вычисления факториала можно записать так:
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 и рекурсия заканчивается.
Рекурсивная процедура или функция должна содержать условие, при котором рекурсия заканчивается (не происходит нового вложенного вызова).