|
|
От: |
LaptevVV
|
|
| Дата: | 04.05.07 14:40 | ||
| Оценка: | 3 (1) | ||
G>Есть ли литература о рекурсии?Рекурсивные функции
Язык C++ предоставляет возможность написания рекурсивных функций, однако целесообразность применения рекурсии оставляется на усмотрение программиста. Как правило, рекурсивные алгоритмы применяются там, где имеется явное рекурсивное определение обрабатываемых данных. Не будем отступать от традиции и рассмотрим функцию факториала n!. Как правило, в программировании её определяют как произведение первых n целых чисел:
n! = 1 * 2 * 3 * ... * n
Такое произведение можно легко вычислить с помощью итеративных конструкций, например, оператора цикла for
//Листинг 7.14. Итеративная функция вычисления факториала long Fact(int k) { long f; int i; for(f = 1, i = 1; i<k; i++) f*= i; return f; }
Однако существует также другое (математическое) определение факториала, в котором используется рекуррентная формула и которое имеет такой вид:
1. 0! = 1
2. Для любого n > 0 n! = n*(n-1)!
Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение
1. F(1) = 1,
2. F(2) = 1,
3. Для любого n > 2 F(n) = F(n-1) + F(n-2)
выглядит для вычислений гораздо лучше, чем прямая формула.
Понятно, что организовать вычисления по рекуррентным формулам можно и без использования рекурсии. Однако, как видно на примерах, представленных в [Шалыто-Программист], преобразование естественной рекурсивной формы в итеративную – довольно сложная задача. Использование рекурсии позволяет легко (почти автоматически) запрограммировать вычисления по рекуррентным формулам. Например, рекурсивная функция для вычисления факториала n! имеет следующий вид.
//Листинг 7.15. Рекурсивная функция вычисления факториала long Fact(int k) { if (k==0) return 1; return (k*Fact(k-1)); // рекурсивный вызов ! }
Аналогично, по указанному определению легко написать функцию вычисления чисел Фибоначчи.
//Листинг 7.16. Рекурсивная функция вычисления чисел Фибоначчи long Fibo(int k) { if ((k==2)||(k==1)) return 1; return (Fibo(k-1)+Fibo(k-2)); // рекурсивный вызов ! }
Рекурсивной функцией называется функция, вызывающая саму себя в своем теле. Необходимо ещё раз подчеркнуть, что «самовызов» будет рекурсивным только в том случае, если находится в теле функции. Как мы видели ранее, «самовызов» в списке параметров не является рекурсивным.
Обычно различают прямую и косвенную рекурсию. Если в теле функции явно используется вызов той же самой функции, то имеет место прямая рекурсия (self-calling), как в приведенных примерах. Если две или более функций взаимно вызывают друг друга, то имеет место косвенная рекурсия. Обычно косвенная рекурсия возникает при реализации программ синтаксического анализа методом рекурсивного спуска.
Прекрасным примером рекурсивной функции является быстрая сортировка Хоора. Сама схема алгоритма является рекурсивной, поэтому написать итеративную программу достаточно сложно, что можно увидеть в книге Н.Вирта "Алгоитмы +данные=программы". Схема функции выглядит так:
void QuickSort(A, 1, n) { //--Выбрать разделяющий элемент с номером 1<k<n //--Разделить массив А относительно k-го элемента QuickSort(A, 1, k-1); //-рекурсивный вызов с левой частью QuickSort(A, k+1, n); //-рекурсивный вызов с правой частью }
Есть большое количество традиционных «игрушечных» задач (ханойские башни, расстановка ферзей и т.п.), которые анализируются в литературе для демонстрации рекурсии. Мы не будем на них останавливаться — гораздо интереснее рассмотреть типично итеративные алгоритмы, которые можно представить рекурсивным образом. В принципе, любой цикл можно заменить эквивалентной рекурсивной программой. В качестве примера рассмотрим рекурсивную реализацию функции вычисления длины строки.
//Листинг 7.17. Рекурсивная функция вычисления длины строки unsigned int Length (char *s) { if (*s==0) return 0; // можно просто !(*s) else return 1+Len(s+1); }
Вызов такой функции абсолютно ни в чём не отличается от вызова аналогичной итеративной, например:
cout<<Len(“1234567890”);
на экран совершенно правильно выводится 10. Работа рекурсивных функций обычно имеет несколько «мистический» оттенок, поэтому не будем пока в деталях разбирать работу этой функции, но обратим внимание на несколько важных моментов:
1. Цикла в функции нет – вместо него у нас имеется рекурсивный вызов. Таким образом, явное повторение заменяется неявным – рекурсивным.
2. Параметр, который является указателем, в рекурсивном вызове увеличивается, перемещаясь к следующему символу.
3. Чтобы такое увеличение не происходило до бесконечности, имеется в наличии условие окончания рекурсии — в операторе if проверяется достижение конца строки.
Эту же функцию можно написать несколько иначе:
unsigned int Length (char *s) { if (*s) return 1+Len(s+1); else return 0; }
И здесь мы наблюдаем те же три перечисленных выше особенности:
1. Вместо цикла имеется рекурсивный вызов;
2. Параметр в рекурсивном вызове изменяется;
3. Условие окончания заменено условием продолжения.
Прежде, чем делать выводы, рассмотрим еще один пример – последовательную обработку файла. Пусть открытие и закрытие файла выполняются в главной программе, а обработка – в отдельной функции, которая последовательно читает записи файла и обрабатывает их. Традиционно такая обработка выполняется в цикле следующего вида:
while (не конец файла) { //-- читать запись //--обработать запись }
Попробуем написать рекурсивную процедуру без использования цикла. Пусть потоковая переменная имеет имя f. Файл представляет собой файл строк – исходный текст самой этой программы, который находится в том же каталоге, что и исполняемая программа.
//Листинг 7.18. Рекурсивная функция обработки текстового файла void ReadFile(ifstream &f) { char s[100]; //--буфер для строки getline(f,s); //--читаем строку cout<<s; //--обработка строки if (!f.eof()) //-пока не конец файла ReadFile(f); //--рекурсивный вызов } int main(void) { ifstream f("recurs.cpp"); ReadFile(f); f.close(); return 0; }
Как мы видим, функция ReadFile несколько отличается от приведенных выше функций – отсутствует явное изменение параметра. Параметр-то все равно изменяется, но неявно — как состояние потока f при чтении. Как и в предыдущих случаях, цикл заменен рекурсивным вызовом, и присутствует условие продолжения.
Формы рекурсивных функций
В общем случае любая рекурсивная функция Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Rec. Как мы видели на примерах, рекурсивный вызов обязательно сопровождался некоторым условием: либо условием окончания, либо условием продолжения. Это понятно, поскольку безусловные рекурсивные вызовы приводят к бесконечным процессам – они сродни бесконечному циклу. Вспомните детский стишок «У попа была собака…» — это как раз случай бесконечной рекурсии. Если реализовать вывод этого стишка как рекурсивную функцию, то она может выглядеть так.
void PriestAndDog(void) { сout<<“У попа была собака, он ее любил.”; сout<<“Она съела кусок мяса, он ее убил,”; сout<<“вырыл яму, закопал и на камне написал:”; PriestAndDog(); }
Теоретически работа этой функции никогда не завершится. На практике программа закончится аварийно по причине переполнения стека (кто хочет – может проверить). Следовательно, главное требование к рекурсивным функциям заключается в том, что вызов рекурсивной функции должен выполняться по условию. Это условие прописывается в операторе if и может быть либо условием продолжения, либо условием окончания. В первом случае в if пишется рекурсивный вызов, во втором — оператор возврата.
Примечание
Это не гарантирует завершение рекурсивной функции – можно совершить другие ошибки. Например, если в определении функции вычисления факториала рекурсивный вызов записан в форме Fact(k--), то при выполнении возникает ошибка переполнения стека при любом способе передачи параметра. В этом случае при рекурсивном вызове берется значение k до уменьшения. В результате происходит вызов с одним и тем же значением параметра, условие никогда не удовлетворяется и рекурсия превращается в бесконечную.
Структура рекурсивной функции может принимать три разных формы (используем условие продолжения):
форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске):
void Rec(void) { S; if (условие) Rec(); }
форма с выполнением действий после рекурсивного вызова (на рекурсивном возврате — подъеме):
void Rec(void) { if (условие) Rec(); S; }
форма с выполнением действий как до (на рекурсивном спуске), так и после рекурсивного вызова (на рекурсивном возврате):
void Rec(void) { S1; if (условие) Rec(); S2; }
В образцах указан заголовок
void Rec(void)
поскольку в данном случае нам важно было продемонстрировать именно формы рекурсивных функций, не отвлекаясь на другие детали. Названия «рекурсивный спуск» и «рекурсивный подъем» связаны с понятием глубины рекурсии (см. далее) – функция спускается на глубину рекурсии и поднимается «оттуда».
Функция вычисления факториала написана в первой форме. Нам удалось написать вторую форму функции, вычисляющей длину строки. Аналогично, поменяв условие, можно преобразовать и функцию вычисления факториала.
//Листинг 7.19. Вторая форма рекурсивной функции вычисления факториала long Fact(int k) { if (k>0) return (k*Fact(k-1)); // рекурсивный вызов ! else return 1; }
Однако переделать функцию чтения файла нам так просто не удастся. Попытка в «лоб» не приносит успеха:
void ReadFile(ifstream &f) { char s[100]; //--буфер для строки if (!f.eof()) //-пока не конец файла ReadFile(f); //--рекурсивный вызов getline(f,s); //--читаем строку cout<<s; //--обработка строки }
Функция становится бесконечной. Конец файла никогда не достигается, поскольку до рекурсивного вызова не выполняется операция чтения. Это наводит на мысль о возможности преобразования данной функции в третью форму – чтение строки выполнять до проверки условия, а вывод строки – после рекурсивного вызова. Попробуем и посмотрим, что получится.
void ReadFile(ifstream &f) { char s[100]; //--буфер для строки getline(f,s); //--читаем строку if (!f.eof()) //-пока не конец файла ReadFile(f); //--рекурсивный вызов cout<<s; //--обработка строки }
Функция работает, но совсем не так как, ожидалось. Строки файла выводятся на экран в обратном порядке! Таким образом, для некоторой рекурсивной задачи подходит отнюдь не любая форма рекурсивной функции. Можно сказать, что для всякой рекурсивной задачи существует естественная для нее форма рекурсивной функции.
Выполнение рекурсивных функций
Несмотря на то, что запись рекурсивных функций бывает очень короткая, они часто страдают неэффективностью. Вспомним, что при каждом вызове в стеке должны быть размещены все параметры и локальные переменные. На эту работу (так же, как и на последующее освобождение) расходуется и время, и пространство – в программу вставляются соответствующие команды, которые выполняются при каждом вызове. Однако эта неэффективность не очень существенна по сравнению с другой – расходом памяти под стек. Поскольку рекурсивный вызов выполняется до окончания выполнения функции – размер стека увеличивается при каждом вызове до тех пор, пока не будет достигнута точка, когда выполняется возврат. Размер стека пропорционален глубине рекрсии. Глубина рекурсии – это максимальная степень вложенности рекурсивных вызовов. В общем случае глубина будет зависеть от входных данных. Например, в рекурсивной функции ReadFile глубина рекурсии определяется количеством строк в читаемом файле. В принципе, это может привести к переполнению стека и аварийному завершению программы. Поэтому при разработке рекурсивных функций необходимо минимизировать количество и размеры локальных переменных и параметров.
Существует также и другая неэффективность – лишние вычисления. В принципе, одним из методов борьбы с такой неэффективностью является сокращение количества рекурсивных обращений в тексте функции: например, если есть такая возможность, вместо двух вызовов оставить только один.
Рассмотрим ещё несколько задач, реализуемых посредством рекурсивных функций, и разберемся более детально в их работе. Пусть требуется написать функцию, определяющую, является ли строка палиндромом (одинаково читающаяся и слева направо, и наоборот). Написание итеративного варианта не представляет сложностей.
bool Palindrom(string s) { int i = 0, j=s.length()-1; for (; i < j; i++, j--) if (s[i]!=s[j]) return false; return true; }
Попробуем преобразовать эту функцию в рекурсивную. Для этого надо сформулировать рекурсивное определение по типу определения факториала. Очевидно, что строка из одного символа является палиндромом. Если символов больше, то строка является палиндромом, если выполняются два условия:
1. первый и последний символы строки s совпадают;
2. строка s без первого и последнего символа является палиндромом.
Для полноты картины и пустую строку будем считать палиндромом. Тогда мы по этому определению можем написать такую рекурсивную схему:
bool Palindrom(string s) { if (s пустая или имеет длина = 1) return true else if (первый символ s == последний символ s) return Palindrom(s без первого и последнего символа) else return false; }
Теперь пишем функцию.
//Листинг 7.20. Рекурсивная функция Palindrom bool Palindrom(string s, int begin, int end) { int end = s.length()–1; if (s.length()=0 || s.length()=1) return true; else if (s[0]==s[end]) return Palindrom(s.substr(1,end-1)); else return false; }
Вызов такой функции может осуществляться, например, так:
cout<<Palindrom("потоп")<<endl;
или так
string s = “потоп”; cout<<Palindrom(s)<<endl;
Теперь разберемся с эффективностью рекурсивной функции. Итеративная форма, очевидно, не делает никаких лишних действий: цикл, в котором сравниваются символы, выполняется либо до середины строки, либо сразу прекращается, если символы не совпали. Возврат выполняется единственный раз. Совсем другое дело – рекурсивная функция. Во-первых, всегда выполняется столько вызовов, сколько символов совпадает в начале и в конце строки. Столько же выполняется и возвратов. Кроме того, при каждом вызове в стек помещаются все параметры и локальные переменные. В нашем случае это строка s. Рассмотрим этот процесс более подробно на примере приведенного выше вызова.
При первом вызове в стек помещается строка «потоп». Поскольку длина строки больше 0, выполняется проверка s[0]==s[end] (буква «п»). Результат равен true, поэтому выполняется return с рекурсивным вызовом
Palindrom(s.substr(1,end-1)).
При втором вызове в стек помещается строка s без первого и последнего символа и локальная переменная end. Снова s[0]==s[end] (буква «о»), поэтому выполняется третий рекурсивный вызов со строкой из одного символа «т». Теперь происходит возврат true из первого if. Однако это выход только из третьего рекурсивного вызова, поэтому мы попадаем во второй вызов и тут же возвращаемся в первй вызов И только после третьего возврата выполняется вывод полученного значения на экран (true, которое выводится как 1).
Теперь рассмотрим рекурсивную реализацию двоичного поиска заданного числа в отсортированном по возрастанию массиве. Двоичный поиск по определению рекурсивен:
— вычисляем середину массива;
— если искомый элемент равен «среднему», то возвращаем результат;
— если искомый элемент меньше «среднего», то выполняем те же действия с левой половиной;
— если искомый элемент больше «среднего», то выполняем те же действия с правой половиной;
Шаги 3 и 4 и будут представлять рекурсивный вызов в программе. Переведем почти «дословно» рекурсивное определение на язык С++ и получим следующее определение функции.
//Листинг 7.21. Рекурсивная функция двоичного поиска в массиве int BinarySearch(const int a[], int b, int e, int k) { if (b==e) return -1; //--не нашли! int c = (b+e)/2; //--середина if (a[c] == k) return c; else if(a[c] > k) c = BinarySearch(a, b,c,k); //--левая половина else if(a[c] < k) c = BinarySearch(a, c+1,e,k);//--правая половина }
Если элемент не найден, то функция возвращает –1. В случае успешного поиска возвращается индекс найденного элемента. В рекурсивных вызовах параметры изменяются, каждый раз сужая область поиска ровно вдвое. Функция имеет первую форму и выполняет все действия на рекурсивном спуске. Пусть в вызывающей программе объявлен массив
int d[] = {1,2,3,4,5,6,7,8,9,10,12,13};
Тогда вызов
int k = BinarySearch(d, 0,12,7);
присвоит переменной k индекс числа 7, равный 6. Функция довольно эффективна, поскольку для массива длиной n элементов выполняет всего log2(n) вызовов функций, при каждом из которых в стек попадают всего 4 параметра.
Данная программа демонстрирует один из важнейших принципов, применямых при разработке рекурсивных функций – «разделяй и властвуй»: в теле функции выполняется два рекурсивных вызова, каждый из которых работает примерно с половиной данных. Подобную схему имеет и быстрая сортировка Хоара. Применяя этот же принцип, попробуем написать функцию вычисления минимума в массиве целых чисел. Итеративное определение не представляет сложностей. При этом даже не требуется оформлять поиск в виде функции – достаточно просто написать в программе следующий цикл:
for(int m=a[0], i=1; i < n; i++) m =((a[i]<m)?a[i]:m);
Данный цикл достаточно эффективен, поскольку за один проход массива гарантированно вычисляется минимум. Количество сравнений на 1 меньше количества элементов массива.
Рекурсивное определение несколько сложнее – без определения функции уже не обойтись, поскольку требуется иметь рекурсивный вызов, заменяющий цикл. Параметрами такой функции, как и в функции двоичного поиска, будет массив и два индекса, определяющие начало и конец обрабатываемого сегмента массива. Взяв за образец функцию двоичного поиска, напишем аналогичную функцию поиска минимума в массиве.
//Листинг 7.22. Рекурсивная функция вычисления минимума в массиве int min(const int a[], int left, int right) { if (left==right) return a[left];//--можно и a[right] int m = (left+right)/2; //--середина int x = min(a, left, m); //--обработка левой половины массива int y = min(a, m+1, right); //--обработка правой половины массива if (x<y) return x; else return y; }
Данная функция имеет третью форму, выполняя действия как на рекурсивном спуске (до рекурсивного вызова), так и на рекурсивном возврате (после рекурсивного вызова). Чисто внешне функция min очень похожа на функцию двоичного поиска, поэтому может создаться впечатление, что она, аналогично двоичному поиску, достаточно эффективно ищет требуемый нам минимум. На самом деле эта функция очень неэффективна. Мы можем посчитать количество и вложенность вызовов, объявив в функции статическую переменную. Увеличивая её при каждом вызове и уменьшая при каждом возврате, можно получить достаточно полную картину рекурсивных вызовов и возвратов. Оформим это в виде процедуры, выводящей на экран количество точек, равное уровню вложенности рекурсивного вывода.
void pp(int& tt, int l, int r) { cout << endl; for(int i = 0; i<tt; i++) cout <<"."; cout <<"min("<<l<<’,’<<r<<’)’; }
Тогда полный «отладочный» вариант функции min теперь выглядит так:
int min(int a[], int left, int right) { static int tt = 0; //--счетчик уровня вложенности pp(++tt, left, right); //--вложенность увеличивается if (left==right) return a[left]; //--можно и a[right] int m = (left+right)/2; //--середина int x = min(a, left, m); //--обработка левой части pp(--tt, left, right); //--вложенность уменьшается! int y = min(a, m+1, right); //--обработка правой части pp(--tt, left, right); //--вложенность уменьшается! if (x<y) return x; else return y; }
Как показывает прогон программы, для массива из 8 элементов вызов min(a,0,7); на экран выводится следующее:
. min(0,7) . . min(0,3) . . . min(0,1) . . . . min(0,0) . . . min(0,1) . . . . min(1,1) . . . min(0,1) . . min(0,3) . . . min(2,3) . . . . min(2,2) . . . min(2,3) . . . . min(3,3) . . . min(2,3) . . min(0,3) . min(0,7) . . min(4,7) . . . min(4,5) . . . . min(4,4) . . . min(4,5) . . . . min(5,5) . . . min(4,5) . . min(4,7) . . . min(6,7) . . . . min(6,6) . . . min(6,7) . . . . min(7,7) . . . min(6,7) . . min(4,7) . min(0,7) //--завершение обработки всего массива
В этом фрагменте увеличение количества точек в очередной строке по сравнению с предыдущей означает рекурсивный вложенный вызов, уменьшение – возврат из вызова.
Попробуем написать более эффективную функцию. Надо вместо двух рекурсивных вызовов постараться оставить только один. Принцип «разделяй и властвуй» в своем «предельном» варианте диктует разделение исходного массива на две неравные части: единственный элемент (первый элемент массива) и остальной массив, размер которого на 1 меньше исходного.
//Листинг 7.23. Эффективная рекурсивная функция поиска минимума int min1(int a[], int begin, int end) { if (begin==end) return a[begin]; int x = min1(a, begin+1, end); if (x<a[begin]) return x; else return a[begin]; }
Эта функция так же, как и предыдущий вариант, выполняет действия как на рекурсивном спуске, так и на рекурсивном возврате. Она значительно эффективнее, поскольку выполняет ровно столько сравнений, сколько у нас имеется элементов в массиве a. В этом можно убедиться, выполнив «отладочную» версию.
. min(0,9) . . min(1,9) . . . min(2,9) . . . . min(3,9) . . . . . min(4,9) . . . . . . min(5,9) . . . . . . . min(6,9) . . . . . . . . min(7,9) . . . . . . . . . min(8,9) . . . . . . . . . . min(9,9) //--х=а[9] . . . . . . . . . min(8,9) . . . . . . . . min(7,9) . . . . . . . min(6,9) . . . . . . min(5,9) . . . . . min(4,9) . . . . min(3,9) . . . min(2,9) . . min(1,9) . min(0,9)
Как мы видим, количество вложенных рекурсивных вызовов равно количеству элементов массива. Глубина рекурсии тоже равна количеству элементов. Сначала до последнего элемента выполняется только рекурсивный спуск. Когда мы достигли последнего элемента – выполняется первый рекурсивный возврат и переменная x впервые получает значение. На первом шаге рекурсивнго подъема переменная x сравнивается сама с собой! Выполняется оператор
else return a[begin];
На рекурсивном подъеме при каждом возврате переменная х сравнивается с предыдущим элементом массива. Таким образом, как это обычно происходит в программировании, за увеличение скорости приходится расплачиваться расходом памяти (в данном случае – увеличением стека).
Рекурсия при обработке динамических структур данных
Динамические структуры данных, вообще говоря, делятся на три больших класса: списки, деревья и графы. Поскольку в каждом классе очень много разных видов (особенно это касается деревьев), мы рассмотрим только линейные списки и двоичные деревья. Эти стуктуры по сути своей являются рекурсивными структурами, писать для них рекурсивные функции достаточно легко.
Односвязный линейный список
Начнем с линейных односвязных списков, рассморенных нами ранее. Пусть информационная часть – поле целого типа:
struct Item { int info; Item* next; };
Для удобства дальнейших записей используем оператор
typedef Item* link;
Как обычно, объявим заголовок списка
link Head; //--звездочка уже не нужна
Имея такие определения, напишем простую функцию вычисления количества элементов списка. Параметром является указатель-заголовок списка.
//Листинг 7.24. Рекурсивный подсчет количества элементов списка long count(link p) { if (p == 0) return 0; return 1 + count(p->next); }
Как мы видим, условием окончания является «пустой» указатель последнего элемента списка. Налицо и изменение параметра – переход по указателю на следующий элемент.
А теперь напишем функцию обхода всех элементов списка в прямом порядке. Для каждого элемента будем вызывать функцию обработки, указатель на которую, естественно, будем передавать в качестве параметра.
//Листинг 7.25. Обработка списка в прямом порядке void visitor(link p, void f(link p)) { if (p == 0) return 0; f(p); //--любая обработка visitor(p->next, f); //--рекурсивный переход к следующему }
В качестве функции обработки может использоваться, например, функция вывода на экран. Или функция, проверяющая некоторые условия, на основании которых может формироваться новый список – вариантов много.
Рекурсия позволяет обходить односвязный список и в обратном порядке – и для этого не нужно вводить в структуру обратный указатель! Вспомним определенную выше функцию ReadFile, которая выводила строки файла в обратном порядке, и поступим аналогичным способом – поменяем порядок рекурсивного вызова и вызова функции обработки.
//Листинг 7.26. Обработка списка в обратном порядке void visitor(link p, void f(link p)) { if (p == NULL) return 0; visitor(p->next, f); //--рекурсивный переход к следующему f(p); //--любая обработка }
Обработка выполняется на рекурсивном возврате, а следовательно – в обратном порядке. Но понятно, что «бесплатного сыра не бывает» — мы расплачиваемся за простоту реализации использованием памяти под стек. Однако попробуйте написать аналогичную итеративную функцию – вы вынуждены будете явно использовать дополнительную память либо под стек, либо для обратных указателей. И вы наживете на свою голову лишние проблемы при отладке. А рекурсия «прячет» стек и позволяет легко и просто совместить прямой и обратный проходы (листинг 7.27).
//Листинг 7.27. Прямая и обратная обработка списка void visitor(link p, void pred(link p), void post(link p)) { if (p == NULL) return 0; pred(p); visitor(p->next, pred, post); //--рекурсивный переход к следующему post(p); }
Двоичное дерево
Двоичные деревья, так же, как и списки, являются по определению рекурсивными структурами. Поэтому использовать рекурсию при обработке деревьев «сам Бог велел». Пусть узел дерева представлен следующей структурой:
struct Node { string name; //--ключ Node *Left; //--«младший» левый сын Node *Right; //--«старший» правый сын };
Как обычно, левый узел содержит значение, меньшее корневого значения, а в правом – большее. Одной из первых задач, которые приходится решать при работе с деревьями, является вывод значений в возрастающем порядке. В «класической» литературе [9,14,16] такие задачи называются «обходом» дерева. Поскольку у нас в каждом узле фигурируют три сущности: корень Root, младший сын Left, старший сын Right, — мы имеем три разных способа обхода дерева:
— Root, Left, Righr; у Вирта [9] такой порядок называется preOrder;
— Left, Root, Righr; у Вирта такой порядок называется inOrder;
— Left, Righr, Root; у Вирта такой порядок называется postOrder.
Эти три вида обхода в точности соответствуют трем формам рекурсивных функций. Естественно использовать для рекурсии условие продолжения. Параметром является указатель на узел – при первом вызове это будет указатель на корень всего дерева. Тогда эти функции выглядят так (листинг 7.28).
//Листинг 7.28. Функции обхода дерева typedef Node* link; void preOrder(link p, void visit(link p)) { if (p!=NULL) //--условие продолжения { visit(p); //--обработка узла preOrder(p->Left); //--пошли налево preOrder(p->Right); //--пошли направо } } void inOrder(link p, void visit(link p)) { if (p!=NULL) //--условие продолжения { inOrder(p->Left); //--пошли налево visit(p); //--обработка узла inOrder(p->Right); //--пошли направо } } void postOrder(link p, void visit(link p)) { if (p!=NULL) //--условие продолжения { postOrder(p->Left); //--пошли налево postOrder(p->Right); //--пошли направо visit(p); //--обработка узла } }
Если вместо функции visit проставить оператор вывода значениея, то функция inOrder как раз выполнит нашу задачу – выведет все значения в возрастающем порядке.
Обратите внимание на то, что во всех функциях обхода используется условие продолжения – рекурсивные вызовы повторяются до тех пор, пока указатель указывает на узел. Такая схема является достаточно типичной при обработке двоичных деревьев. Попытки реализовать аналогичные процедуры итеративного вида убеждают нас, что без явного использования стека обойтись трудно.
Нужно сказать, что фактически все процедуры обработки деревьев в той или иной мере используют один из вариантов обхода —- как при вставках, так и при удалениях необходимо выполнять поиск места в дереве, где выполнять операцию. В качестве примера приведем функцию поиска в бинарном дереве заданной строки [16]. Функция поиска имеет два параметра: указатель на узел дерева и искомую строку. Функция возвращает указатель на узел, в котором найдена заданная строка. Если строка не найдена, то возвращается NULL. В этой функции естественно используется первая форма рекурсивной процедуры: сначала выполняются действия (сравнение заданной и искомой строки), а затем происходит рекурсивный вызов.
//Листинг 7.29. Поиск в двоичном дереве link Search(link p, char *name) { int cmp; if (p==NULL) return NULL; //--не нашли! cmp = strcmp(name, p->name); if (cmp==0) return p; //--нашли! else if (cmp < 0) Search(p->left, name); //--пошли налево else Search(p->right, name); //--пошли направо }
Приведем еще несколько простых рекурсивных алгоритмов, применяемых к двоичным деревьям. Например, подсчет узлов в дереве можно осуществить, выполнив следующую функцию.
//Листинг 7.30. Поэсчет узлов в дереве unsigned long count(link p) { if (p==NULL) return 0; return count(p->Left) + 1 + count(p->Right); }
Возвращаемый тип unsigned long позволяет нам обрабатывать очень большие деревья. Такой же простой является функция подсчета высоты дерева.
//Листинг 7.31. Вычисление высоты дерева typedef unsigned long ul; ul h(link p) { if (p==0) return 0; //--пустое дерево или дошли до листа ul x = h(p->Left); //--высота левого поддерева ul y = h(p->Right); //--высота правого поддерева if (x > y) return x+1; //-- +1 от корня к левому поддереву else return y+1; //-- +1 от корня к правому поддереву }
И в той и в другой функции используется условие окончания – рекурсивные вызовы прекращаются
Параметры в рекурсивных функциях
Параметры в рекурсивные функции можно передавать во всех возможных формах.В рассмотренных выше примерах они передавались по значению. Указатели, обычно используютс при обработке массивов, однако сами-то указатели передаются по значению. Возникает ещё несколько вопросов:
— Можно ли присвоить начальные значения параметрам рекурсивных функций?
— К каким последствиям может привести передача в рекурсивную функцию параметра по ссылке?
Ответ на первый вопрос очевидно положительный — простой пример с факториалом подтверждает это. Допустим, в нашей программе надо вычислять факториалы, но чаще всего требуется значение 10!. Тогда мы можем явно прописать 10 как значение по умолчанию:
long Fact(int k=10) { if (k>0) return k*Fact(k-1); else return 1; }
Вызов функции работает самым обычным способом:
cout <<Fact(6)<<endl; cout <<Fact()<<endl;
Первый вызов выводит на экран число 720, а второй – значение 10!, равное 3628800. Как обычно, начальное значение может вычисляться с помощью некоторой функции. И наиболее интересный случай – вызов той же самой рекурсивной функции для вычисления начального значения. Только, как мы помним, надо впереди прописать прототип, например:
double Fact(double k); double Fact(double k=Fact(4)) { if (k>0) return k*Fact(k-1); else return 1; }
Вызов функции работает как обычно. В этой функции надо обратить внимание на следующие особенности:
— Вызов функции в списке параметров не является рекурсивным вызовом этой функции, несмотря на то, что сама функция является рекурсивной. Фактически вызов той же функции на месте параметра означает F(F(x)). В нашем случае имеем (4!)!=24!;
— Мы поменяли тип возвращаемого значения на double, поскольку 24! – это значительно больше, чем предельно допустимая величина unsigned long. Кстати, знаете ли вы, какой максимальный факториал вычисляется на 32-разрядном Pentiume? Всего 1754!. Это число имеет порядок 104930, а тип его должен быть long double.
— Нам потребовалось поменять и тип параметра на double, чтобы присвоение значения параметру произошло корректно. Иначе возникают проблемы при выполнении.
Заметим, что и в рекурсивных функциях можно использовать фокус с операцией запятая при вызове — на месте единственного параметра может в скобках через запятую стоятьнесколько выражений. В функцию, как обычно, передается последнее выражение.
Для ответа на второй вопрос, определим функцию вычисления факториала с параметром-ссылкой.
//Листинг 7.32. Передача параметра ссылки в рекурсивную функцию double Fact(unsigned int& k) { if (k==0) return 1; return (k*Fact(k-1)); }
Если у нас определена переменная
int n = 5;
то вызов Fact(n) даст 120, и n останется равным 5. Тогда в чем проблема? Немного изменим программу:
double Fact(unsigned int& k) { if (k==0) return 1; return (k*Fact(--k)); // рекурсивный вызов ! }
Рекурсивный вызов Fact(k-1) превратился в Fact(--k). С точки зрения вычисления факториала ничего не изменилось. Однако после этого вызова значение переменной n уменьшится на 1. Функция имеет побочный эффект изменения переменной, переданной в качестве параметра. Поэтому после вызов Fact(n) переменная n станет равной нулю. Вариант функции с передачей параметра по значению работает совершенно корректно и при втором варианте рекурсивного вызова.
