Что такое рекурсия?
Программисты вкладывают в это понятие следующий смысл: рекурсия - это прием программирования, при котором программа вызывает саму себя либо непосредственно, либо косвенно.
Обычно начинающий программист, впервые услышавший про рекурсию, впадает в легкое замешательство. Казалось бы, нет ничего более бессмысленного, чем рекурсия. Подобная цепочка вызовов никогда не завершится из-за зацикливания, или в лучшем случае завершится, но аварийно, когда задача исчерпает все наличные ресурсы компьютера.
На самом деле рекурсия - это тонкий и изящный инструмент, который при умелом использовании способен сослужить добрую службу программисту.
Почему именно рекурсия?
Действительно, почему именно рекурсии выпала честь удостоиться отдельной статьи? Разве это не рядовой прием программирования, один из многих?
Лично я выделяю рекурсию из общего ряда по многим причинам. Вот некоторые из них:
* Прежде всего, рекурсия красива. Первоначальное знакомство с ней может вызвать непонимание и легкий шок, но, овладев этим механизмом, вы вряд ли в дальнейшем сможете избежать соблазна пользоваться им время от времени. Изящество рекурсии в программировании я могу сравнить только с изяществом метода индукции в математике.
* Многие структуры, как искусственного, так и естественного происхождения, рекурсивны по самой своей сути. Рассмотрите ветви и корни деревьев, структуру сложной организации, иерархию классов в сложной программе, фракталы - в любой из этих структур вы найдете многочисленные повторения целого в части. Таким образом, многие сущности естественным образом могут быть смоделированы рекурсивными структурами. А чем же еще обрабатывать рекурсивную структуру, как не рекурсивной процедурой?
* Немало задач имеет также рекурсивную природу. Даже, пожалуй, большинство нетривиальных задач. По крайней мере, в программировании далеко не нов метод декомпозиции задачи на несколько более простых, те, в свою очередь, разделяются на еще более простые, и так до тех пор, пока не дойдем до элементарных частей, решить которые достаточно просто. Естественно, программисты не являются монополистами в этой области: подобными методами пользуются архитекторы, машиностроители, математики
Несмотря на все эти достоинства, рекурсия отнюдь не спешит прописаться в арсенале средств многих программистов, даже профессиональных (под профессионализмом в данный момент я подразумеваю отнюдь не степень мастерства, а факт, что именно программирование дает данному человеку средства к существованию), имеющих о ней самое смутное представление.
Любое незнание обычно порождает массу предрассудков. Например, шаман племени людоедов, не имея представления об атмосферном электричестве, объясняет благодарным соплеменникам, что гроза - это проявление немилости богов. И его слова принимаются за истину в первой инстанции, ибо природа не терпит пустоты, - там, где нет знания, поселяется суеверие.
Рекурсия также обросла слухами и суевериями. Вы можете услышать от компьютерных шаманов, что она:
* безмерно расточительно относится к памяти (забавно, но я слышал эти доводы много лет назад, программируя на мини-ЭВМ PDP-11/40, которая "щедро" отводила на пользовательскую задачу около 50Кбайт; периодически меня пытаются запугать этим и сейчас, когда объем ОЗУ в 1 Гбайт не является чем-то из ряда вон выходящим);
* весьма накладна по ресурсам процессора; при этом факт, что производительность микропроцессоров Intel за минувшие 10 лет возросла как минимум в 100 раз (если судить только по тактовой частоте, не учитывая прогресс архитектуры), как-то совершенно не принимается во внимание;
* наконец, сложна в реализации и отладке, что влечет за собой массу ошибок в программе; то, что ошибки в задании условий для циклов с пред- и постусловиями, а также начальных и конечных значений в циклах с перебором значений обычно изобилуют в типичной нерекурсивной программе, конфузливо замалчивается.
Итак, попробуем разобраться, что же представляет собой рекурсия на самом деле.
Первый опыт рекурсии
По сложившейся традиции для первого знакомства с рекурсией почти все авторы, не сговариваясь, приводят два примера: вычисление факториала и поиск чисел Фибоначчи. Должен заметить, что с точки зрения практикующего программиста рекурсивное вычисление факториала весьма уступает обычному итерационному способу. Лично убедившись в этом, новичок обычно на этом и заканчивает знакомство с рекурсией, предпочитая потратить время на изучение более практичных вещей.
Не будем отступать от традиции и мы. При этом, разумеется, примем вышесказанное к сведению и постараемся воспринять следующий пример просто как иллюстрацию к простейшему применению метода, а вовсе не как призыв весь остаток жизни вычислять факториалы именно таким образом.
Итак, вспомним, что такое факториал. Обозначается факториал восклицательным знаком "!" и вычисляется следующим образом:
N! = 1 * 2 * 3 * * (N-1) * N, (1)
то есть представляет собой произведение натуральных чисел от 1 до N включительно.
На эту функцию можно посмотреть и под другим углом зрения. Внимательнее изучив формулу (1), мы можем прийти к выводу, что
N! = N * (N-1)! (2)
Таким образом, мы определили факториал через сам факториал! Казалось бы, такое определение совершенно бесполезно, так как неизвестное понятие определяется через опять же неизвестное понятие, и мы приходим к бесконечному циклу. Однако это впечатление обманчиво, потому что на самом деле факториал "N" определяется через факториал (N-1), то есть нахождение неизвестной функции сводится к вычислению той же неизвестной функции от другого аргумента, на единицу меньшего, чем исходный. Таким образом, есть надежда, что каждая следующая задача будет решаться чуть легче предыдущей.
Окончательно разорвать замкнутый круг мы сможем, если дополним рекурсивное определение (2) еще одним, которое служит чем-то вроде тупика, предназначенного для остановки процесса:
1! = 1 (3)
(На самом деле следовало бы оговорить поведение факториала в нуле и при отрицательных значениях аргумента, но, поскольку в данный момент мы знакомимся с рекурсией, а не создаем коммерческую библиотеку математических функций, опустим несущественные детали).
Правила (2) и (3) совместно позволяют вычислить значение факториала от любого аргумента. Попробуем для примера вычислить значение 5!, несколько раз применив правило (2) и однократно правило (3):
5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1
Мы получили результат, который совпадает с определением (1) с точностью до перестановки сомножителей. (И самой перестановки в принципе можно было бы избежать, если перейти в (1) от правосторонней рекурсии к левосторонней, но эти разновидности мы обсудим позже).
Как же выглядит рекурсия на практике? Попробуем реализовать рекурсивное вычисление факториала в виде функции на C:
Код:
long int Fact(long int N)
{
if (N < 1) return 0;
else if (N == 1) return 1;
else return N * Fact(N-1);
}
Как видим, реализация функции ничем принципиально не отличается от рекурсивного определения факториала.
На этом рекомендую сделать некоторую паузу, скопировать текст функции Fact в вашу любимую систему разработки на языке C и несколько раз прогнать ее под отладчиком в пошаговом режиме; если вы владеете отладчиком на уровне работы с регистрами процессора и областями оперативной памяти, рекомендую понаблюдать также за метаморфозами, происходящими в стеке.
Рекурсия и итерация: две стороны одной медали
Большинство из тех, кто прочитал все вышеописанное, наверняка уже задались вопросом: а зачем все это нужно? Ведь первоначальное определение факториала ничуть не хуже, выглядит гораздо привычнее, да и реализовать его в общем-то не сложнее:
Код:
long int Fact2(long int N)
{
long int F = 1;
for (long int i=2; i<=N; i++)
F *= i;
return F;
}
Такая реализация наверняка покажется гораздо более естественной почти всем программистам. Исключение, пожалуй, составит немногочисленная братия, программирующая на языках Lisp и Prolog, для которых рекурсивное мышление стало привычным ввиду особенностей применяемых инструментов.
На самом деле, разбираясь в столь детских по уровню примерах, мы затронули гораздо более глубинное и серьезное явление, а именно - эквивалентность рекурсии и итерации.
В теоретическом программировании существует теорема, которая гласит, что рекурсия и итерация эквивалентны. Это значит, что любой алгоритм, который можно реализовать рекурсивно, с таким же успехом может быть реализован и итеративно, и наоборот. Тем, кто знаком с теорией формальных языков, теорией конечных автоматов и подобными дисциплинами, она наверняка хорошо известна. Остальным придется поверить мне на слово, тем более что мы только что убедились в ее истинности на простейшем примере.
Следует ли из этого, что мы попусту потратили время, я - на написание данной статьи, вы - на ее прочтение? Не означает ли вышесказанное, что программисту достаточно владеть только приемами итерации для решения любых задач, поскольку она эквивалентна рекурсии?
Тут нам придется признать как факт, что теоретики программирования привыкли манипулировать довольно абстрактными понятиями: вместо компьютера они используют машины Тьюринга, машины Поста и подобные сооружения, которые вы вряд ли приобретете в ближайшем компьютерном салоне. Соответственно, вместо программы у них - алгоритм (строго говоря, они не эквивалентны, ибо далеко не каждая программа является алгоритмом). При этом в центре внимания в первую очередь находится корректность алгоритма, об эффективности особенно не пекутся, ибо все, что требуется от алгоритма, - это завершиться за конечное время, а уж насколько оно велико, теоретиков мало волнует, - вычисления на машине Тьюринга все равно обходятся им даром.
Мы же с вами живем в реальном мире, который далеко не столь идеален: наши компьютеры обладают конечными ресурсами, за ограничения которых нам не выйти, а потребители наших программ - конечным терпением, границы которого переходить тоже чревато. Поэтому мы вынуждены обращать внимание на такие низменные материи, как эффективность вычислений. А обратив на нее более пристальное внимание, мы будем неприятно поражены фактом: несмотря на якобы обещанную эквивалентность, рекурсивный вариант вычисляет факториал куда медленнее, чем его итеративный собрат! Более того, и памяти при работе он потребляет куда больше.
Итак, оставим рекурсию теоретикам, а сами прекрасно обойдемся и без нее? Именно к такому выводу приходят многие после изучения соответствующего раздела учебника программирования, в котором красуются все те же рекурсивные факториалы и числа Фибоначчи. Но не будем спешить с выводами. На самом деле есть очень много примеров, подобных вышеприведенному, в которых применение рекурсии просто расточительно и не выдерживает никакой конкуренции с рекурсией. Однако существует немало и противоположных примеров, для которых рекурсивное решение просто и элегантно, а итеративное громоздко и неестественно. Задача программиста не только овладеть обоими подходами, но и научиться выбирать, какой из них применить в данном случае. Лично я, к сожалению, не могу предложить вам на этот счет готового рецепта; интуиция и чувство меры вот на что я обычно полагаюсь в подобных ситуациях.
Итак, до сих пор мы рассматривали рекурсию на примере, рекурсивная реализация которого на практике малополезна. Теперь, осознав основные идеи, лежащие в основе рекурсии, приступим к рассмотрению задач, для решения которых она действительно полезна.
Когда рекурсия выгодна
В общем случае наилучшее применение рекурсии - это решение задач, для которых свойственна одна черта: решение задачи в целом сводится к решению подобной же задачи, но меньшей размерности и, следовательно, легче решаемой.
Поскольку эта фраза звучит довольно загадочно и абстрактно, постараюсь проиллюстрировать ее примером подобной задачи. Хрестоматийный вариант - игра Ханойские башни.
Легенда гласит, что где-то в Ханое находится храм, в котором размещена следующая конструкция: на основании укреплены 3 алмазных стержня, на которые при сотворении мира Брахма нанизал 64 золотых диска с отверстием посередине, причем внизу оказался самый большой диск, на нем чуть меньший и так далее, пока на верхушке пирамиды не оказался самый маленький диск. Жрецы храма обязаны перекладывать диски по следующим правилам:
* За один ход можно перенести только один диск.
* Нельзя класть больший диск на меньший.
Руководствуясь этими нехитрыми правилами, жрецы должны перенести исходную пирамиду с 1-го стержня на 3-й. Как только они справятся с этим заданием, наступит конец света.
Попытаемся и мы внести свою лепту в этот процесс. Сначала попытаемся построить абстрактную модель процесса переноса части пирамиды (когда мы с ней справимся, станет яснее, как перенести пирамиду целиком).
Итак, решаем обобщенную задачу: как перенести пирамиду из n колец со стержня i на стержень j, пользуясь стержнем k как вспомогательным? Эта задача решается следующим образом:
* Перенести (n-1) кольцо с i на k.
* Перенести 1 кольцо с i на j.
* Перенести (n-1) кольцо с k на j.
Выглядит уже немного знакомо, не правда ли? Задача переноса n колец решается через перенос (n-1) кольца. Осталось только добавить тривиальное граничное условие для вырожденного случая переноса пустой пирамиды из 0 колец, чтобы наш алгоритм завершился, а не отправился в минус бесконечность.
Реализуем алгоритм на любезном многим языке C:
Код:
void TowerMove(// перенос пирамиды
int n, // из n дисков
short i, // со стержня i
short j, // на стержень j,
short k // используя стержнень k как вспомогательный
)
{
// проверка граничного условия пустую пирамиду не перемещаем
if (!n)
return;
TowerMove(n-1, i, k, j);
// переносим одно кольцо фактически это TowerMove(1, i, j, k);
printf("%2d - %2d\n", i, j);
TowerMove(n-1, k, j, i);
}
Функция TowerMove фактически способна переместить пирамиду из любого количества колец, в том числе и всю исходную. Для решения задачи в целом нам остается всего лишь дописать главную функцию:
Код:
int main(int argc, char* argv[])
{
TowerMove(5, 1, 3, 2);
return 0;
}
Как нетрудно догадаться, в данном случае решается задача переноса пирамиды из 5 колец с 1-го стержня на 3-й.
Рекурсивная обработка рекурсивных структур
Собственно, предпосылкой для написания данной статьи явился наш диалог с Dimyan'ом (полностью увидеть его можно здесь). Для тех, кто не намерен перечитывать его целиком и вникать в детали, краткий пересказ проблемы.
Имеется некая иерархическая структура, хранимая в реляционной базе данных. (Вообще хранение иерархических структур в реляционной базе данных это отдельная, достаточно интересная сама по себе тема, но она не имеет непосредственного отношения к данной статье; возможно, мы к ней вернемся в одной из статей по базам данных, а пока примем на веру, что это вполне возможно).
Необходимо визуально представить ту структуру в виде классического отображения дерева подобно тому, как это сделано в Проводнике MS Windows.
Древовидная структура - яркий пример рекурсивной структуры. Каждый узел дерева может быть представлен как корень дерева меньшего размера. Значит, отображение каждого узла подобно отображению дерева в целом. А из этого следует, что рекурсивная процедура в данном случае вполне уместна.
Заранее прошу прощения у приверженцев C, но очередной пример будет представлен на языке C#. Причина проста программа должна работать с базой данных, а реализация подобных программ как на C, так и на C++ занятие не для слабонервных. Разумеется, детали работы с базой данных я здесь приводить не буду. Исходный текст процедуры приведен полностью на форуме (см. ссылку выше), а весь тестовый проект, если у кого-то возникнет желание воспроизвести его на своем компьютере, я могу выслать почтой по запросу.
Код:
private void FillBranch(TreeNode tn)
{
// получить список дочерних узлов для tn
// выбираем из базы данных все вершины, у которых значение поля ParentID
// совпадает со значением тега текущего узла tn
.
.
.
// строим список узлов
ArrayList nodeList = new ArrayList();
.
.
.
// все дочерниу узлы для tn занесены в nodeList
// добавить все дочерние узлы к текущему
foreach (TreeNode nn in nodeList)
{
tn.Nodes.Add(nn);
FillBranch(nn);
} // foreach
}
Как видите, основная идея остается неизменной. Для того, чтобы построить ветку дерева с корнем в узле tn, нужно:
* найти все дочерние узлы для tn;
* добавить их к дереву;
* построить дерево с корнем в каждом из дочерних узлов.
Как я уже говорил ранее, для рекурсивных процедур весьма важно, чтобы на каком-то уровне вложенности дальнейшие вызовы прекращались, в противном случае произойдет зацикливание до тех пор, пока пространство стека не будет исчерпано (в стеке хранятся формальные параметры процедуры, локальные переменные с автоматическим размещением, а также некоторая служебная информация, необходимая для корректного возврата из процедуры). Чаще всего для этого используется условный оператор (как в случае с факториалом или Ханойскими башнями). Но в нашем примере условный оператор отсутствует. Однако зацикливания не происходит, т.к. его роль неявно выполняет оператор цикла foreach: когда мы добираемся до листовых вершин дерева, которые не имеют дочерних, список nodeList станет пустым и цикл не выполнится, предотвратив таким образом очередные рекурсивные вызовы процедуры. С этого момента начнется обратная раскрутка цепочки рекурсивных вызовов, пока не дойдет до первоначального вызова для корня всего дерева.
Результат работы процедуры показан на рисунке:
Перебор с возвратом
Еще один класс задач, которые целесообразно решать рекурсивными методами, - это задачи, для решения которых не существует определенного алгоритма. В этом случае приходится искать решение методом проб и ошибок, подобно поиску выхода из лабиринта. Кстати, аналогия тут прямая, поскольку, блуждая в лабиринте, мы регулярно забредаем в тупик и вынуждены возвращаться обратно и искать другой путь. При этом, если мы не хотим кружить в нем вечно, нам следует помечать уже обследованные ветви, чтобы не возвращаться к ним вновь.
Итак, уже накатанная последовательность действий: обследовать лабиринт - значит обследовать каждую из его ветвей. Дойдя до развилки, повторять алгоритм рекурсивно, возвращаясь из тупиковых ветвей. Если лабиринт не содержит циклов, рано или поздно вы найдете путь на волю. Если содержит, алгоритм немного усложняется, но все рано приводит к цели.
Если желаете поупражняться в рекурсии, попробуйте самостоятельно составить программу, находящую выход из ациклического лабиринта.
Реальные задачи, конечно, обычно посложнее, чем просто хождение по лабиринту. Однако в целом поиск решения практически такой же: мы делаем очередной шаг в поиске решения, фиксируем его и пытаемся на его основе сделать следующий. Не найдя решение, мы должны попробовать другой допустимый шаг. Если все возможные шаги уже перебраны, а решение так и не найдено, следует отступить на шаг назад и повторить процедуру поиска. Подобная стратегия применима, например, в логических играх, где игровое пространство и множество допустимых ходов ограничено правилами игры.
Попробуем и мы решить простенькую задачу. Условие ее таково. Дана квадратная доска, разделенная на клетки, размером n*n клеток наподобие шахматной. В одном из ее углов расположен шахматный конь. Требуется ходом коня пройтись по всей доске, побывав на каждом поле ровно по одному разу.
Прежде всего нам потребуется доска. Сделаем ее классом и поместим его интерфейс в файл Board.h:
Код:
/*
описание шахматной доски, по которой будет перемещаться конь
*/
const int MaxLen = 10; // максимальный размер доски
class CBoard
{
private:
unsigned short m_Size; // актуальный размер доски
unsigned short m_Cell[MaxLen][MaxLen]; // собственно ячейки доски - каждая клетка содержит номер хода
public:
CBoard(unsigned short n);
virtual ~CBoard();
bool CheckFree(short i, short j); // проверка клетки i, j на предмет возможности хода
void Move(short x, short y, unsigned short n); // пометить клетку i, j как занятую ходом n
void MoveBack(short x, short y); // пометить клетку i, j как свободную
void Dump(void); // вывод доски на печать
unsigned short CellsCount(void); // кол-во клеток на доске
};
Функциональность класса доски довольно нехитрая. Кроме создания и уничтожения объекта, доска может сообщить о состоянии отдельной клетки (свободно/занято), пометить клетку как занятую, узнать количество клеток на доске, а также вывести на консоль состояние всех клеток доски.
Реализацию класса поместим в файл Board.cpp:
Код:
#include "Board.h"
#include <stdio.h>
#include <stdlib.h>
CBoard::CBoard(unsigned short n): m_Size(n)
{
if (n <= MaxLen)
{
for (unsigned short i=0; i<n; i++)
for (unsigned short j=0; j<n; j++)
m_Cell[i][j] = 0;
}
else
{
printf("Board size is too big!\n");
exit(1);
}
}
CBoard::~CBoard()
{
}
bool CBoard::CheckFree(short i, short j)
{
return
( (i >= 0)
&& (j >= 0)
&& (i < m_Size)
&& (j < m_Size)
&& (0 == m_Cell[i][j])
);
}
void CBoard::Move(short x, short y, unsigned short n)
{
m_Cell[x][y] = n;
}
void CBoard::MoveBack(short x, short y)
{
m_Cell[x][y] = 0;
}
void CBoard::Dump(void)
{
for (unsigned short i=0; i<m_Size; i++)
{
for (unsigned short j=0; j<m_Size; j++)
printf(" %3d", m_Cell[i][j]);
printf("\n\n");
}
printf ("\n");
}
unsigned short CBoard::CellsCount(void)
{
return m_Size * m_Size;
}
Думаю, что реализация доски не должна вызвать никаких вопросов. Конечно же, функцию подсчета клеток на доске можно сделать и поэффективнее, вычислив произведение один раз в момент создания объекта, а не перемножая одно и то же при каждом обращении к функции. Но все же в фокусе нашего внимания сегодня рекурсия, а не оптимизация шахматных досок, поэтому оставим ее в первозданном виде.
Теперь наступил черед реализации коня. Интерфейс класса тоже не отличается сложностью (файл Knight.h):
Код:
#include "Board.h"
// шахматный конь
class CKnight
{
private:
CBoard *m_pBoard;
short MoveX(unsigned short i);
short MoveY(unsigned short i);
public:
CKnight(CBoard *b);
virtual ~CKnight();
// сделать ход n на клетку x, y
void Move(short x, short y, unsigned short n);
// отменить ход
void MoveBack(short x, short y);
// попытка сделать ход n на клетку x, y
bool Try(short x, short y, unsigned short n);
};
Реализация класса располагается в файле Knight.cpp:
Код:
#include "Knight.h"
#include <stdio.h>
CKnight::CKnight(CBoard *b): m_pBoard(b)
{
}
CKnight::~CKnight()
{
m_pBoard = 0;
}
void CKnight::Move(short x, short y, unsigned short n)
{
m_pBoard->Move(x, y, n);
}
void CKnight::MoveBack(short x, short y)
{
m_pBoard->MoveBack(x, y);
}
// попытка сделать ход n на клетку (x,y)
bool CKnight::Try(short x, short y, unsigned short n)
{
Move(x, y, n);
// все возможные ходы сделаны - успех
if (n == m_pBoard->CellsCount())
return true;
// попытаться сделать следующий ход
bool res = false;
for (unsigned short i=0; i<8; i++)
{
// сгенерировать след. ход
short x1 = x + MoveX(i);
short y1 = y + MoveY(i);
// Проверить на допустимость
if (m_pBoard->CheckFree(x1, y1))
{
// попытаться его сделать
res = Try(x1, y1, n+1);
// если ход успешный, прекратить дальнейший перебор
if (res)
break;
// неудачный ход - стереть его
MoveBack(x1, y1);
}
}
return res;
} // Try
short CKnight::MoveX(unsigned short i)
{
static short x[] = {-1, 1, 2, 2, 1, -1, -2, -2};
return x[i];
}
short CKnight::MoveY(unsigned short i)
{
static short y[] = {2, 2, 1, -1, -2, -2, -1, 1};
return y[i];
}
Методы Move и Moveback тривиальны и просто делегируют соответствующие методы класса CBoard.
Методы MoveX и MoveY, возможно, нуждаются в некоторых комментариях. Они реализуют правила хода коня, точнее, выдают смещения относительно текущей позиции по горизонтали и вертикали. Представим фрагмент доски в виде таблицы, при этом символ "*" символизирует текущую позицию коня, а цифры - номер допустимого хода:
1 2
8 3
*
7 4
6 5
Думаю, этой иллюстрации вполне достаточно для понимания их реализации.
Самый интересный из методов - это, конечно же, Try. Собственно, ради его рассмотрения все и затевалось. Построение этого метода довольно типично для данного класса задач:
* зафиксировать ход;
* проверить, не найдено ли решение, и вернуть значение истина, если да;
* генерировать допустимые правилами следующие ходы и пробовать их;
* если следующий ход увенчался успехом, прекратить перебор, иначе стереть его и продолжить перебор;
* если все ходы перебраны и решение не найдено, вернуть значение ложь.
Теперь у нас есть все необходимое для решения поставленной задачи. Дело за малым - написать основную программу. Она весьма проста (файл Main.cpp):
Код:
// Knight.cpp : Defines the entry point for the console application.
//
//
#include <stdio.h>
#include <string.h>
#include "Knight.h"
int main(int argc, char* argv[])
{
printf("Knight Program\n\n");
CBoard brd(5);
CKnight kn(&brd);
bool b = kn.Try(0, 0, 1);
if (b) // решение найдено
brd.Dump(); // вывести его
else
printf("No solution found...\n");
return 0;
}
ЗаключениеТема рекурсии, пожалуй, столь же неисчерпаема, сколь и число приложений, где ее применение делает программы ясными, компактными и изящными (а что эти свойства значат для программ, вы можете узнать в разделе, посвященном переводам статей Дейкстры). Если вы попробовали выполнить приведенные примеры, то наверняка имели возможность лично убедиться в том, что слухи о прожорливости к ресурсам и низкой эффективности рекурсии несостоятельны.
Весьма показательно было бы также попытаться решить те же задачи посредством итерации. Это наглядно продемонстрирует, что теоретическая эквивалентность итерации и рекурсии может быть не так уж легко достижима на практике.
К сожалению, объем статьи получился уже значительным, да и времени на ее подготовку потребовалось немало. Поэтому пора ставить точку, хотя тема, на мой взгляд, не исчерпана полностью.
Если вы находите тему интересной и полезной для себя и хотели бы продолжить разговор о рекурсии, оставьте свои пожелания на форуме. Материал как минимум еще на одну статью найдется без труда.
Alf
Information
- Posted on 31.01.2010 22:05
- Просмотры: 3186