§4. Введение в рекурсивные функции.

Различают косвенную и прямую рекурсии.

Функция называется косвенно рекурсивной, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функциии. Заметим, что в таком случае по тексту программы её косвенная рекурсия может быть не фидна.

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

Пример 1. (+) Целое положительное число перевести в двоичную систему счисления, используя алгоритм деления на два.

int x=15;

void To2rec(unsigned );

int main ()

{ unsigned a, y=1;

gotoxy(2,y++);

cin>>a;

To2rec(a);

getch();

return 0;

}

void To2rec(unsigned n)

{

int n2;

if (!n) return ;

n2=n % 2;

gotoxy(x--,wherey());

cout<<n2;

n=n/2;

To2rec(n);

}

Как выполняется такая функция? Пусть из головной программы в функцию To2rec передали число 20. Так как !n=!20 ложно, то retun не выполняется, получаем 20%2=0 и выводим его. После этого n=20/2=10 и функция вызывает саму себя с параметром 10. Аналогично !10 тоже ложно, получаем 10%2=0 и выводим его. Затем функция вызывается с параметром 5 и так далее. Если получим n=0, с помощью return возвращаемся в функцию main.

Замечание. Составить самостоятельно нерекурсивный алгоритм перевода целого числа из десятичной в двоичную системы счисления (см. первый семестр) и сравнить их.

Пример 2. (+) Пусть F₀=1, F₁=1. Для заданного k>1 вычислить F_k по формуле:

F_k=F_k-1+ F_k-2., где k=2,3,4, …

int FRec(int k)

{ if (k==0 || k==1) return 1;

return FRec(k-1)+FRec(k-2);

}

int main ()

{ int N=10;

cout<<FRec(N);

getch();

return 0;

}

Выполнение таких функций состоит из двух этапов. Первый (прямой ход) заключается в погружении алгоритма (функции) “самой в себя”. Например, для вычисления F₁₀ функция обращается к самой себе дважды: с параметром 9 и параметром 8. Аналогично для вычисления F₉ функция обращается к самой себе также дважды: с параметром 8 и параметром 7. Этот процесс продолжается, пока не выполним return 1 из функции Frec.

На втором этапе (обратный ход) выполняется выход из рекурсии. В нашем примере для N=10 вычисляются последовательно значения 1+1=2, 1+2=3, 2+3=5, и т.д., 34+55=89.

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

Рекурсивные алгоритмы эффективны в тех задачах, где рекурсия используется в определении обрабатываемых данных. Поэтому серьёзное изучение рекурсивных алгоритмов нужно проводить, вводя и используя такие динамические структуры данных с рекурсивной структурой, являющиеся видами списков, как стеки, деревья, очереди и другие. Такие алгоритмы будут рассмотрены на втором курсе.