Программирование на языке C рекурсия

Слово рекурсия буквально означает возврат. Когда вы смотрите в зеркало, имея позади себя другое зеркало, то видите бесконечно повторяющуюся серию изображений. Каждое изображение является отражением (рекурсией) света от предыдущего.

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

Некоторые алгоритмы рекурсивны по своей природе. Например, факториал числа равен произведению предшествующих ему последовательных чисел. Так, факториал числа 5 равен 1*2*3*4*5=120. В общем случае факториал n равен произведению n на факториал n-1. Учитывая этот факт, вы можете написать рекурсивную функцию факториала следующим образом:

double Fectorial (int nmber)

{

if (nmber > 1)

return nmber * Fectorial(nmber-1);

return 1;

}

Функция Fectorial() возвращает значение типа double и объявляет единственный параметр nmber типа int. Вначале оператор if проверяет значение параметра nmber. Если nmber больше единицы, функция возвращает значение nmber, умноженное на факториал nmber - 1. Таким образом, функция Fectorial() вызывает саму себя со значением аргумента меньшим на единицу. Когда nmber станет равен единице, выполнится оператор return 1 (факториал единицы равен 1), и рекурсия начнет «разворачиваться».

Замечание. Используйте пошаговый режим отладчика, чтобы лучше понять, как работает рекурсия.

Следующая простая программа демонстрирует ключевые особенности рекурсии. Введите данный код, скомпилируйте и запустите его. На экране вы увидите счет значений от 1 до 10. Постарайтесь понять, как программа использует рекурсию, чтобы справиться с этой задачей.

#include <stdoi.h>

void Recount(int top);

main ()

{

Recount (10);

return 0;

}

void Recount(int top)

{ //<

if (top > 1)

Recount(top - 1);

printf("%4d", top);

}

В строке 7 вызывается функция Recount(), которая использует рекурсию, чтобы посчитать от 1 до 10 (никто не станет спорить, это нелегкий путь для решения простой задачи).

В строке 13 проверяется значение параметра top. Если оно больше единицы, функция вызывает себя в строке 14, передавая top - 1 в качестве нового аргумента. Когда значение top уменьшится до нуля, строка 15 отобразит значение этой переменной.

Заметьте, что на экране отображается десять значений, стало быть, оператор printf() выполнился десять раз. Это показывает, что каждый рекурсивный вызов завершается возвратом к точке вызова, выполняя оператор printf() один раз для каждого вызова функции Recount().

Если рекурсивная функция объявляет какие-нибудь локальные переменные, то эти переменные повторно создаются на каждом уровне рекурсии. Например, если функция А() объявляет локальную переменную i, то, когда А() вызывает себя, в стеке создается совершенно новая переменная i.

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