Рекурсия. Экспериментальное изучение.
Здесь я исследую некоторые стороны известного программистского фокуса по названием «рекурсия». Хотя, возможно, некоторые из этих вопросов и рассматривались уже, но, по крайней мере, я постараюсь взглянуть на них несколько по-другому.
Где-то в Интернете мне как-то встретилось высказывание – чтобы понять рекурсию, нужно понять рекурсию. Источник (или адрес) я к сожалению не записал. Что-то в этом несомненно есть. В рекурсии есть какой-то загруз, который ставит человеческий разум в тупик.
1)
Классификация
рекурсии по местоположению повторного входа (структура кода рекурсивной
функции).
Рассмотрим программу. Она написана на языке Си++ (конкретнее – Visual C++ 5.0, как консольное приложение). Особых изысков в интерфейсе нам здесь не нужно, главное – проиллюстрировать принципы.
Отмечу еще – некоторые функции, которые есть в исходном коде программы, вам незнакомы. Это естественно – я их когда-то придумал сам. И теперь вставляю просто для простоты, чтобы не ломать лишний раз себе голову. Я уверен, что они работают правильно. Вы отнеситесь к этому так же, как компилятор – уперлись в незнакомую функцию – что ж, по всему видно (то-есть исходя из синтаксиса), что это какая-то функция, пусть и незнакомая. Что она делает – я вкратце поясню. А до внутреннего строения в общем то нет никакого дела, главное, чтоб она работала. А вы, если захотите откомпилировать у себя этот пример, и у вас не будет библиотеки, где “сидит” эта функция – можете придумать что-то свое.
Уточним встречающиеся функции. StrCat – ее аргументы представляют собой указатели на char. Первая строка (на нее указывает первый аргумент) дописывается в конец второй. Фактически тоже самое делает стандартная функция языка Си strcat. Функция CpStr – это копирование первой строки во вторую (т.е. по адресу второй). И наконец WrStr – это запись строки в конец указанного файла (и закрытие его потом). Один из аргументов (в программе обозначен как End – это символ конца строки). Вы можете воспользоваться комбинациями стандартных функций для производства тех же действий.
Я постараюсь обратить внимание на структуру рекурсивной функции. Прежде всего выделим в ее теле раздел инициализации. Он в общем-то наименее интересный – инициализируются некоторые нужные в дальнейшем переменные, и все. Далее – стоп-секция. Она проверяет, не пора ли на выход (из этой самой рекурсии). Далее идет Do-секция (первая) – в ней выполняется полезная работа. Потом повторный вход в рекурсивную функцию (вызов самой себя). И, наконец, вторая Do-секция. Там также выполняется некоторая полезная работа.
Название «Do-секция» я придумал сам. Можно заменить его русскоязычным термином «рабочая секция».
Обратим внимание на то, что в программе есть три счетчика. Счетчик I увеличивается в стоп-секции, он определяет, когда выходить из рекурсии. Счетчик J увеличивается (инкрементируется) в первой Do-секции, перед повторным входом в рекурсию. Это так называемый режим «хвостовой» рекурсии. И последний счетчик K увеличивается во второй Do-секции, после повторного входа в рекурсию (режим «вложенной» рекурсии).
При выходе из рекурсии программа записывает в файл слово «Return!».
/*********************/
#include <stdio.h>
#include <stdlib.h>
#include "Str_ex.h"
int I=0;
int J=0;
int K=0;
char S[120];
char S1[120];
char A[20];
char A1[20];
char End[3];
void F(void)
{
/*
Initialization */
End[0]=13;
End[1]=10;
End[2]=0;
S[0]=0;
/*
End of initialization */
/*
Stop-section */
if(I>5)
{
StrCat("
Return! ",S);
WrStr("Test_Rec.txt",End,S,1);
return;
}
I++;
/*
End of Stop-section */
/*
Do-section */
CpStr("A ",S);
sprintf(A,"J= %d",J);
J++;
StrCat(A,S);
StrCat(" ",S);
sprintf(A,"I= %d",I);
StrCat(A,S);
WrStr("Test_Rec.txt",End,S,1);
/* End of Do-section*/
F();
/*
Do-section N2 */
CpStr("B ",S1);
sprintf(A1,"K= %d",K);
K++;
StrCat(A1,S1);
StrCat(" ",S1);
sprintf(A1,"I= %d",I);
StrCat(A1,S1);
WrStr("Test_Rec.txt",End,S1,1);
/* End of Do-section N2*/
return;
}
void main(void)
{
F();
return;
}
/*********************************/
Вот результат ее действия (что она пишет в файл):
A J= 0 I= 1
A J= 1 I= 2
A J= 2 I= 3
A J= 3 I= 4
A J= 4 I= 5
A J= 5 I= 6
Return!
B K= 0 I= 6
B K= 1 I= 6
B K= 2 I= 6
B K= 3 I= 6
B K= 4 I= 6
B K= 5 I= 6
Теперь изменим программу. Уберем вторую Do-секцию. Останется лишь хвостовая рекурсия.
/*********************/
#include <stdio.h>
#include <stdlib.h>
#include "Str_ex.h"
int I=0;
int J=0;
int K=0;
char S[120];
char S1[120];
char A[20];
char A1[20];
char End[3];
void F(void)
{
/*
Initialization */
End[0]=13;
End[1]=10;
End[2]=0;
S[0]=0;
/*
End of initialization */
/*
Stop-section */
if(I>5)
{
StrCat("
Return! ",S);
WrStr("Test_Rec.txt",End,S,1);
return;
}
I++;
/*
End of Stop-section */
/*
Do-section */
CpStr("A ",S);
sprintf(A,"J= %d",J);
J++;
StrCat(A,S);
StrCat(" ",S);
sprintf(A,"I= %d",I);
StrCat(A,S);
WrStr("Test_Rec.txt",End,S,1);
/* End of Do-section*/
F();
return;
}
void main(void)
{
F();
return;
}
/*********************************/
Вот что получается в файле:
A J= 0 I= 1
A J= 1 I= 2
A J= 2 I= 3
A J= 3 I= 4
A J= 4 I= 5
A J= 5 I= 6
Return!
А теперь оставим лишь вторую Do-секцию. То-есть программа представляет собой вариант вложенной рекурсии.
/*********************/
#include <stdio.h>
#include <stdlib.h>
#include "Str_ex.h"
int I=0;
int J=0;
int K=0;
char S[120];
char S1[120];
char A[20];
char A1[20];
char End[3];
void F(void)
{
/*
Initialization */
End[0]=13;
End[1]=10;
End[2]=0;
S[0]=0;
/*
End of initialization */
/*
Stop-section */
if(I>5)
{
StrCat("
Return! ",S);
WrStr("Test_Rec.txt",End,S,1);
return;
}
I++;
/*
End of Stop-section */
F();
/*
Do-section N2 */
CpStr("B ",S1);
sprintf(A1,"K= %d",K);
K++;
StrCat(A1,S1);
StrCat(" ",S1);
sprintf(A1,"I= %d",I);
StrCat(A1,S1);
WrStr("Test_Rec.txt",End,S1,1);
/* End of Do-section N2*/
return;
}
void main(void)
{
F();
return;
}
/*********************************/
Вот что получается в файле:
Return!
B K= 0 I= 6
B K= 1 I= 6
B K= 2 I= 6
B K= 3 I= 6
B K= 4 I= 6
B K= 5 I= 6
Кстати, последний оператор return, который не входит не в одну секцию, можно убрать из программы.
В некоторых задачах (например программирование компиляторов) возможна и более сложная структура рекурсивных функций.
2)
Исследование
глубины рекурсии.
Изменим нашу программу. Теперь она представляет собой запуск вложенной рекурсии (правда в тексте ее я уже не буду выделять секции). Обратим внимание, что рекурсивная функция F имеет один целый параметр.
/****************************************/
#include <stdio.h>
#include <stdlib.h>
#include "Str_ex.h"
int I=0;
void F(int n)
{
char
S[120];
char
A[20];
char
End[3];
End[0]=13;
End[1]=10;
End[2]=0;
S[0]=0;
CpStr("A
",S);
if(I>10000) return;
I++;
sprintf(A,"n=%d",n);
StrCat(A,S);
StrCat(" ",S);
sprintf(A,"I=%d",I);
StrCat(A,S);
WrStr("Test_Rec.txt",End,S,1);
F(n+1);
return;
}
void main(void)
{
F(1);
return;
}
/*******************************/
В Windows 98 программа заканчивается с
сообщением об ошибке («Программа выполнила недопустимую операцию и будет
закрыта»), и в файле оказывается 6657
записей. То-есть рекурсия с целым параметром функции прогоняется 6657 раз.
В Windows 2000 Pro – 6631 раз (кстати, на моем 2-гигагерцовом компьютере Пентиум-4 с 256 мегабайтами оперативки эта программа выполнялась около 4-5 минут).
Вот сообщение об ошибке, выскакивающее в отдельном окошке:
“Исключение unknown software exception
(0x00000fd) в приложении по адресу 0x77fcc114.
А вот содержимое результирующего текстового файла, который программа заполняет записями:
A n=1 I=1
A n=2 I=2
A n=3 I=3
A n=4 I=4
……..
……..
A
n=6627 I=6627
A
n=6628 I=6628
A
n=6629 I=6629
A
n=6630 I=6630
A n=6631 I=6631
Если в функции 2 int-параметра, то она выполняется 6465 раз. Если 3 целых параметра – то 6307 раз (это все для Windows 2000 Pro).
Если же вообще нет параметров, все равно, к сожалению, функция выполняется только 6805 раз (это, напоминаю, для Windows 2000 Professional).
Снова результаты опытов на Windows 98:
Один параметр типа int – 6657 (это я уже повторяюсь),
Два параметра int – 6490
Без параметров – 6832.
Это все на машине с Pentium 2, 192 М оперативки.
В операционной системе Windows 95 все точно так же (хотя машина во много раз слабее – Pentium-166, 16 М.
Теперь для Windows 2000 Server (машина – та же, что и для Windows 98):
Один параметр типа int – 6631 (как и для Professional – смотри выше),
Два параметра int – 6465
Без параметров – 6806.
Никаких сообщений об ошибке Win2k Server не выдает – просто программа заканчивает работу и все.
Дополнения:
1. Интересно было бы знать, есть ли некая «ручка», которая регулирует глубину рекурсии. Может где-то в свойствах компиляторов… По крайней мере в Visual C++ 5.0 я ничего такого не нашел.