Заметки о рекурсии

[Dimyan]

Alf, спасибо
Статья великолепная, и я говорю это обьективно, потому что пока ты ее готовил я успел кое что уже почитать
И заявляю, что все что я нашел о рекурсии по сравнению с твоей статьей просто отжимается  :twisted:
Конкретно мне понравился стиль изложения и обилие примеров .
Не могу сказать что узнал прекрасный метод программирования - рекурсию, я ее знал, НО я ее понял наконец то! В купе с кодом по загрузке дерева, который как ты и рекомендовал я прошел по шагам в дебагере я могу с уверенностью заявить что теперь я знаю что такое рекурсия и могу применять ее на практике!
Еще я понял чего действительно не хватает для понимания рекурсии, нужно просто представить ее в обьеме, пройти по шагам не в дебагере а в голове, вот тогда после прояснения картины, она как родная становится

[Dimyan]

Да, и еще:
Я нахожу тему интересной и с ОГРОМНЫМ удовольствием узнал бы побольше о рекурсии

[Alf]

Dimyan, молодчина, что не пожалел сил и разобрался!  

Значит, не зря я потратил время на написание статьи... Тем более что ты сам убедился, что интересный готовый материал по этой теме найти практически невозможно, нужно все из памяти вытаскивать по крошкам, что когда-то попадалось.

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

В основном в дальнейшем будем говорить о практическом применении рекурсии. Главное - это научиться узнавать задачи, которые выгодно решать рекурсивно.

Если хочешь поупражняться в рекурсии, вот тебе несколько задач (я думаю привести их в качестве примеров к последующим статьям; если решишь их достаточно быстро, опубликуем твое решение, если не получится - сверимся, что именно вызвало затруднения).

1) Задача о восьми ферзях.
Имеется шахматная доска 8*8 клеток и 8 ферзей. Нужно расставить ферзей таким образом, чтобы ни один из них не мог побить другого. (Заимствовано у Вирта из книги "Алгоритмы + структуры данных = программы").

2) Сравнение строки с шаблоном.
Задана произвольная текстовая строка и шаблон, который помимо символов может содержать метасимволы "?" (заменяет любой символ) и "*" (заменяет любую, в том числе пустую, последовательность символов), подобно шаблонам имен файлов. Нужно определить, соответствует ли строка шаблону.
Например,
"dfgjr" и "d*kc" не соответствуют, а
"dgjryseaerdt" и "dg*er?t" - соответствуют.
(Задача взята из реальной жизни, когда несколько лет назад мои знакомые делали собственную поисковую систему. Человек, считавший себя гуру С++, заключил со мной пари на ящик импортного пива, что напишет более компактную и корректную программу, но неумение работать с рекурсией привело его к проигрышу).

3) Раскраска географической карты.
Дана плоская географическая карта. Нужно раскрасить ее таким образом, чтобы никакие два региона, имеющие общую границу, не были окрашены одним цветом (как обычно и красятся карты). Необходимо при этом использовать минимальное количество красок.
Есть теорема (доказанная относительно недавно), что ЛЮБУЮ карту можно покрасить всего четырьмя красками. Проверь ее в деле! (Заимствовано из книги Ч. Уэзерелла "Этюды для программистов").

[Алексей++]

доказанная относительно недавно

а я не видел доказательства - где можно посмотреть?
(те книги, где я встречал эту теорему, она была ещё в статусе - "не имеет доказательств, но работает")

[Гром]

Alf, сбрось мне на мыло пожалуйста функцию сравнения которую ты писал по рекурсии - дабы время сэкономить - началось у меня опять - поджимает немного!
Вот это!!!

2) Сравнение строки с шаблоном.

[Alf]

Alf, сбрось мне на мыло пожалуйста функцию сравнения которую ты писал по рекурсии - дабы время сэкономить - началось у меня опять - поджимает немного!
Вот это!!!

2) Сравнение строки с шаблоном.

Гром, это было почти 10 лет назад, где-то в 1995-м, на Borland C++ 3.1 под DOS... Само собой, с тех пор очень мало что уцелело, даже дискеты тогдашние 5.25 дюйма уже не читаются...  
Но надеюсь, что программировать с тех пор не разучился  
Если тебе нужно для дела, то с этой задачи как раз и начну.

[Alf]

доказанная относительно недавно

а я не видел доказательства - где можно посмотреть?
(те книги, где я встречал эту теорему, она была ещё в статусе - "не имеет доказательств, но работает")

Вот первое упоминание доказательства, которое мне удалось найти: Steen L.A. Solution of the Four Color Problems. Mathematics Magazine, 49, 4, September 1976.
Должен сказать, что доказательство не из тех ,которые поражают изяществом: вначале было доказано, что все возможные конфигурации сводятся к 1936 случаям, а затем было проверено при помощи компьютера, что каждый из этих случаев может быть раскрашен 4-мя красками.
Чтобы не быть голословным, цитирую самих авторов, Аппеля и Хакена: "Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно".

[Dimyan]

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

2) Времени сейчас не много, но попробую сделать вторую задачу (про сравнение строк), она мне понравилась, к тому же я считаю что она имеет большую практическую ценность

P.S.: Повспоминал свои старые программы написанные на C++ Builder и ужаснулся над моим придумыванием велосипеда, ведь сколько было гемороя (реально помню две таких программки, ох и помучался я с ними), а все могло решится элегантной рекурсией

[Never]

Добралась, наконец реально прочитать твою статью. Альф- нет слов: просто здорово написал. Я, конечно, в тебе и не сомневалась,  но все-таки - статья вышла просто СУПЕР!!!
Дальше? Конечно- надо!

[Alf]

Всем спасибо за теплые отзывы о статье  
Честно говоря, я и сам получил большое удовольствие в процессе ее написания, уж больно изящная тема, и почему-то совершенно незаслуженно обойденная вниманием...

Dimyan, давай сделаем так: поскольку Грому решение задачи по сопоставлению строкии шаблона нужно прямо сейчас, то я сегодня вечером напишу его по памяти и отправлю ему, но обнародовать не буду, чтобы не навязывать тебе свой подход. Когда твое решение будет готово, мы их сопоставим. Уверен, ты будешь просто изумлен красотой и компактностью функции.
Кстати, если найдется кто-то желающий представить итеративное решение этой или остальных задач, милости просим. Думаю, сравнение этих двух подходов будет весьма познавательным.

Всем: если у кого есть интересные задачи и вы подозреваете, что рекурсия подходит для их решения, - присылайте, попробуем решить их вместе. Чтобы продолжение статей о рекурси не заглохло, нужны интересные и полезные на практике примеры.

[Dimyan]

Alf, у меня уже кое что получилось (точнее все работает), но зашел в тупик с алгоритмом сравнения при введенной звездочке (*), с этим пока никак

[Гром]

Alf, я в принципе могу и сам написать - но если по ходу пойдет то очень даже было бы не плохо поиметь функцию в которую введя две строки с * ? получить ответ равны или нет...
Заранее Спасибо.

А за статьи твои не просто спасибо, а ОГРОМНОЕ спасибо.
Мне очень приятно сознавать, что такие люди как ты здесь!!!

[Alf]

Dimyan, покажи, что уже получилось.
А "звездочка"-то и есть изюминка в этой программе. Если бы не она, то и без рекурсии бы превосходно обошлись, просто шли по строкам и посимвольно сравнивали. Чуть сложнее стандартной strcmp.

Гром, если есть идеи, как писать такую функцию, поделись. Интересно сравнить разные подходы. А вечером я тебе свой вариант вышлю.

[Dimyan]

Только вот это

Код:

private void Comparison(int Length)
		{
			if((Length+1)<= textBox1.Text.Length)
			{
				if(((textBox1.Text[Length] == textBox2.Text[Length])||(textBox2.Text[Length]=='?')))
				{
					Length++;
					Comparison(Length);
				}
				else
				{
					MessageBox.Show("Строки не равны");
				}
				
			}
			else MessageBox.Show("Строки равны");

		}

[Alf]

Dimyan, мне не понравилось...  

Во-первых, ты двигаешься по обеим строкам синхронно, поскольку у тебя параметр Length задается как текущая позиция символа для обеих строк. Если в шаблоне попадется "*", она может заменить любое количество символов в строке, и с этого момента у тебя указатели текущей позиции должны разойтись. Поэтому их должно быть два с самого начала - для каждой из строк.

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

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

Вот тебе небольшая наводка, как делал я.
Представь строку в виде "первый символ" + "хвост". То же самое сделай и с шаблоном. А потом рассмотри, при каких условиях строка соответствует шаблону при таком подходе. Там всего-то несколько вариантов получается, и все либо простые, либо очень простые.

[Dimyan]

Хорошо попробую

[Alf]

Dimyan, Гром, набросал вчера функцию сопоставления строки и шаблона. Вот что у меня получилось:

Код:

const char asterisk = '*';
const char question = '?';
const char endofline = '\0';

bool PattCmp(const char *s, const char *p)
{
  if (!*s && !*p)
    return true;
  else if (!*p)
    return false;
  else if (!*s)
    return ((asterisk == *p++) && (endofline == *p));
  else if (asterisk == *p)
  {
    if (endofline == *++p)
      return true;
    else
    {
      bool f;
      do
        f = PattCmp(s++, p);
      while (!f && *s);
      return f;
    }
  }
  else if (question == *p)
    return PattCmp(++s, ++p);
  else
    return (*p == *s) ? PattCmp(++s, ++p) : false;
}

Набросал по-быстрому, поэтому мог ошибиться. Если кто найдет входные данные, которые неправильно обрабатываются, сообщите мне, буду благодарен, т.к. функция пойдет примером в следующую статью о рекурсии.
Напоминаю, что в шаблоне помимо обычных символов могут быть два метасимвола: "?" заменяет любой символ, "*" - любую последовательность символов (в том числе пустую).

[npak]

Красиво!  Получил большое удовольствие, разбираясь в твоей функции.

В POSIX есть аналогичная функция fnmatch, заточенная под сравнение имён файлов.  Но у меня нет под руками сорсов glibc, чтобы сравнить.

[Alf]

Красиво!  Получил большое удовольствие, разбираясь в твоей функции.

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

В POSIX есть аналогичная функция fnmatch, заточенная под сравнение имён файлов.  Но у меня нет под руками сорсов glibc, чтобы сравнить.

Интересно было бы сравнить. Мне попадались подобные функции для имен файлов, но они имели ограничения на вид шаблона (например, не более одной звездочки и т.п.)

[Гром]

Alf, я проверю, мне как раз это будет надоть!!!!

[Джон]

Рекурсия, примененная к месту, всегда чертовски красива

   

"To iterate is human, to recurse divine" L. Peter Deutsch
("Итерация свойственна человеку, рекурсия - божественна")

А ты говоришь... "чертовски"

[Alf]

Джон, поскольку рекурсия мне тоже некоторым образом свойственна (чему есть многочисленные свидетели), не мог же я сказать, что она "божественно красива". Окружающие сочтут это нескромным, мол, сам себе скрытый комплимент делаю  
А так вроде нейтрально получилось, даже учтиво по отношению к коллеге из преисподней  

[Гром]

Alf,  

[Джон]

Понимаю - единство и борьба противоположностей -  

[ysv_]

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

Alf, при следующих данных твоя функция возвращает неправильный результат: PattCmp("", "**");

[Гром]

ysv_, добавь проверку - if (strlen(first_str) == 0) return false;

[ysv_]

ysv_, добавь проверку - if (strlen(first_str) == 0) return false;

ГРОМ, Так она и возвращает false, а должна true.

[Гром]

Неа - строка не содержащая ничего не должна возвращать что равна содержащей строке - тут ты не прав!

Если я проверяю ввденный параметр на наличие двух букв - с пустой строкой - как они могут быть равны???

[ysv_]

* - обозночает любое количество букв, в том числе - н_у_л_е_в_о_е. О!

[Alf]

Гром, формально ysv_ прав - звездочка может означать пустую строку, и любое количество звездочек подряд - тоже.

ysv_, спасибо за тест, придется подлатать 3-й return.

Гром, вопрос к тебе, как к потенциальному потребителю функции: где она будет применена и имеет ли смысл в этом приложении сравнивать пустую строку с шаблоном? Можешь привести реальный пример?