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

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

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

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

Пример 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.

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

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

Упражнения, тесты.

1. Дан прототип функции:

float FunSum(float a, float b, float h, float (*F)(float)); //1

и вещественная функция одной переменной:

float Fun1(float x) {return x/(1+x*x*x); }

Какие из следующих вызовов функции FunSum синтаксически правильные?

1) float S; S=FunSum(-1, 1, 0.1, Fun1);

2) float S; S=FunSum(-1, 1, 0.1, Fun1(x));

3) float a=-1., b=1., h=0.1; cout<<FunSum(a, b, h, Fun1);

4) float f=Fun1(x); cout<<FunSum(-1, 1, 0.1, f);

5) float f; f=Fun1(x); cout<<FunSum(-1, 1, 0.1, &f);

6) ошибка в прототипе функции, то есть в //1.

2. Дан прототип функции:

float FunSum(float a, float b, float h, float (*F)(float)); //1

Какие из следующих вызовов функции F из FunSum правильные?

1) float S, x; S=F(x);

2) float S, x; S=*F(x);

3) float S, x; S=(*F)(x);

4) float S, x; S=(*F(x));

5) float x; F(x);

6) float x; *F(x);

7) float x; (* F)(x);

8) float x; (* F(x));

9) float S, x; S=(*F)(x);

10) float S, x; S=(&F)(x);

3. В каком из следующих вариантов объявлен указатель на функцию с двумя параметрами (строка и целое число) и возвращающей один символ?

1) char *PFun2 (char *, int);

2) char (*PFun2) (char *, int );

3) char *PFun2 (char t[] , int k);

4) char (*PFun2) (char *t , int k);

5) char (*PFun2) (char t[], int k);

6) char *(*PFun2) (char t[], int);

7) char *(*PFun2) (char *, int);

8) char PFun2 (char *, int);

4. Дано следующее объявление: char *(*PFun2) (char *, int); Что объявлено?

Варианты ответов:

1) Указатель на функцию с параметрами типа строка и типа int, возвращающую значение типа указатель на char, то есть строку.

2) Указатель на функцию с параметрами типа строка и типа int, возвращающую один символ.

3) Указатель на функцию, параметрами которой являются символ и целое число и возвращающей значение типа указатель на char, то есть строку.

4) Функция с параметрами типа строка и типа int, возвращающая значение типа указатель на char, то есть строку.

5) Указатель на указатель на функцию с параметрами типа строка и типа int, возвращающую один символ.

5. Даны прототипы следующих трёх функций:

void Fun1 (float); void Fun2(float); void Fun3(float);

В каком из вариантов правильно объявлен и проинициализирован статический массив указателей на функции (размерность — константа)?

1) const n=3; void (*far[n])( float)= { Fun1, Fun2, Fun3 };

2) const n=3; void (*far)( float) [n]= { Fun1, Fun2, Fun3 };

3) const n=3; void *far[n]( float)= { Fun1, Fun2, Fun3 };

4) void (*far[3])( float t); far[0]= Fun1; far[1]= Fun2; far[2]= Fun3 ;

5) const n=3; void (*far[n])( float t)= { Fun1(t), Fun2(t), Fun3(t) };

6) void (*far[3])( float t); far[0]= Fun1(t); far[1]= Fun2(t);

far[2]= Fun3(t) ;

7) const n=3; float (*far[n])( float)= { Fun1, Fun2, Fun3 };

6. Даны тексты двух функций

double MyExp (double x) { return (exp(x)); };

double Myq(double x) { return x*x; };

Третья функция — встроенная (стандартная) для вычисления значения функции cos. В каком из вариантов правильно объявлен, создан и проинициализирован динамический массив указателей на функции размерности три?

1) int n; cin>>n; double **fun(double )= new (double (*[n])(double));