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

[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.

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

[Гром]

ysv_, Alf,

По стандарту записи
*  - ОДИН любой символ - он не может быть пустым - пустой бывает строка - пустой символ = НОНСЕНС - ибо = нет символа!!!

? - означает любые символы в любом колличестве - т.е. в том числе и пустые!!!!

Стандарт содран с bash shell и cmd prompt  - и не спорьте - это не ИМХО - это 100%

Alf, прога называется shell локальный шелл - правила нужны стандартные!!!!

[Alf]

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

[ysv_]

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

Вот решение с помощью итерации:

bool CompareText(const char*& s, const char*& p)
{
  while (*s!=0 && *p!=0 && *p!='*')
  {
    if (*s!=*p && (*p!='?' || *s==0)) return false;
    ++p;
    ++s;
  }
  if (*p=='*') return true;
  return (*s==0 && *p==0);
}

void SkipAsterisk(const char*&p)
{
  while (*p=='*') ++p;
}

bool FindText(const char*& s, const char*& p)
{
  const char *ss, *pp;
  while (*s!=0)
  {
    ss=s;
    pp=p;
    if (CompareText(ss, pp))
    {
      s=ss;
      p=pp;
      return true;
    }
    ++s;
  }
  return false;
}


bool PattCmp2(const char* s, const char* p)
{
  if (!CompareText(s, p)) return false;
  SkipAsterisk(p);
  while (*s!=0 && *p!=0)
  {
    if (!FindText(s, p)) return false;
    SkipAsterisk(p);
  }
  return (*s==0 && *p==0);
}

[Гром]

Падон перепутал - действительно * любой симовл ? один!!!!

Прашу прастить великадушна !  

[Alf]

ysv_, у меня сравнение любой строки со звездочкой через PattCmp2 выдает отрицательный результат.

[npak]

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

Интересно сравнить разные подходы.

Идея для итеративного подхода -- выписать конечный автомат, который распознаёт строки по заданному шаблону.  Получится, конечно, не классический конечный автомат, так как здесь будут две входных последовательности (шаблон + строка), но здесь это не так важно.

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

[Alf]

Еще раз благодарю ysv_ за участие в тестировании функции.
Для того, чтобы пустая строка соответствовала шаблону ***... (из произвольного количества звездочек), следует 3-й условный оператор заменить на

Код:

  else if (!*s)
    return ((asterisk == *p++) && ((endofline == *p) || PattCmp(s, p)));

Итак, функция в целом приобретает вид:

Код:

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) || PattCmp(s, 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;
}

[ysv_]

Подправленный вариант Alf'а:
const char asterisk = '*';
const char question = '?';
const char endofline = '\0';

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


Исправленный итеративный вариант:
bool CompareText(const char*& s, const char*& p)
{
  while (*s!=0 && *p!=0 && *p!='*')
  {
    if (*s!=*p && (*p!='?' || *s==0)) return false;
    ++p;
    ++s;
  }
  if (*p=='*') return true;
  return (*s==0 && *p==0);
}

bool FindText(const char*& s, const char*& p)
{
  if (*p==0) return true;
  const char *ss, *pp;
  while (*s!=0)
  {
    ss=s;
    pp=p;
    if (CompareText(ss, pp))
    {
      s=ss;
      p=pp;
      return true;
    }
    ++s;
  }
  return false;
}


bool PattCmp2(const char* s, const char* p)
{
  if (!CompareText(s, p)) return false;
  while (*s!=0 && *p!=0)
  {
    SkipAsterisk(p);
    if (!FindText(s, p)) return false;
  }
  SkipAsterisk(p);
  return (*s==0 && *p==0);
}

Как видно - решение с помощью рекурсии - раза в три компактнее.

[Гром]

Alf, даешь статью по конечным автоматам !
Ты у нас по теории подвязался!!

[Alf]

ysv_, предложенный итеративный вариант по-прежнему отказывается сопоставлять непустую строку с шаблоном, оканчивающимся на '*'.

Что касается предложенного исправления рекурсивной функции, то теперь она выдает соответствие при сопоставлении пустой строки с шаблоном "*?", чт на мой взгляд неправильно.

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

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

[Alf]

Alf, даешь статью по конечным автоматам !
Ты у нас по теории подвязался!!

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

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

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

Итак, возможные темы для следующих статей:

1. Теория формальных языков, конечные автоматы и т.п.
2. Рекурсия.
3. Базы данных (теория).
4. Базы данных (ADO.NET).
5. SADT, UML и т.п.
6. Нотации IDEF0, IDEF3, IDEF1X и их применение при разработке программ.

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

P.S. Кстати, а как быть при голосовании, если хочешь проголосовать сразу за несколько вариантов? Допускает это движок сайта, или каждый может выбрать только лишь один?

[npak]

Предчувствия меня не обманули.  

Автомат получился недетерминированным.  Недетерминизм появляется в том случае, когда за звёздочкой в шаблоне идёт символ.  Например '*a'.

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

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

[npak]

Мои 2 копейки -- рекурсивный и итеративный варианты на C.

Код:

const char asterisk = '*';
const char question = '?';

int
end_of_string(const char * str)
{
    return (*str == '\0');
}

int
skip_asterisks( const char ** p_pat )
{
    int result = 0;
    const char * pat = *p_pat;

    while ( *pat == asterisk ) pat ++;
    result = ( pat != *p_pat );
    *p_pat = pat;
    return result;
}

//
// RECURSIVE
//

int
match_pattern_recursive(const char * pat, const char * str)
{
    while ( !end_of_string( pat ) )
    {
        if ( *pat == asterisk )         // *
        {
            int result;

            // Glob all asterisks into one; jump to the next non-asterisk char
            // or end of the string
            skip_asterisks( &pat );

            // Optimization: empty pattern after asterisk matches any string
            if ( end_of_string( pat ) ) return 1;
            
            if ( end_of_string( str ) )
            {
                // Empty string matches only empty pattern
                return ( end_of_string( pat ) );
            }
            // Try to match the rest of pattern anywhere in string.
            while ( !( result = match_pattern_recursive( pat, str ) )
                    && !end_of_string( str ) )
            {
                // Move forward along the string (asterisk eats the string).
                str ++;
            }
            return result;
        }
        else if ( *pat == question )    // ?
        {
            if ( end_of_string( str ) )
            {
                return 0;
            }
            // Matches any char
            str ++; pat ++;
        }
        else                            // Any meaningful char
        {
            if ( end_of_string( str ) || *str != *pat )
            {
                return 0;
            }
            str ++; pat ++;
        }
    }
    // Pattern is empty here.  Note that the last char in the pattern (if any)
    // was not asterisk (see optimization above).  Therfore the only match is
    // an empty string.
    return end_of_string( str );
}

//
// ITERATIVE
//

int
match_pattern_header( const char ** p_pat, const char ** p_str )
{
    const char * pat = *p_pat;
    const char * str = *p_str;

    while ( !end_of_string( pat ) && !end_of_string( str ) )
    {
        // Came across an asterisk.  It means that fixed part matches.  Good
        // verdict.
        if ( *pat == asterisk )
        {
            *p_pat = pat;
            *p_str = str;
            return 1;
        }
        // Non-matching symbols found.  Bad verdict.
        if ( *pat != question && *pat != *str ) return 0;
        // Ok, proceed to the next symbol.
        pat ++; str ++;
    }

    // We can get here if and only if at least one string is over.
    // Good verdict if they are both empty or the next char in pattern is an
    // asterisk.
    if ( ( end_of_string( str ) && ( end_of_string( pat ) ) )
         || *pat == asterisk )
    {
        *p_pat = pat;
        *p_str = str;
        return 1;
    }
    return 0;
}

int
match_pattern_iterative( const char * pat, const char * str )
{
    int match = 1;
    int after_asterisk = 0;
    
    while ( match && !end_of_string( pat ) )
    {
        after_asterisk = skip_asterisks( &pat );
        
        if ( !after_asterisk )
        {
            match = match_pattern_header( &pat, &str );
        }
        else
        {
            // Try to match the next sub-pattern anywhere in the string.
            while ( !( match = match_pattern_header( &pat, &str ) )
                    && !end_of_string( str ) )
            {
                str ++;
            }
        }
    }
    // Here: match == 0 (means we failed to find a match to a certain
    //                   sub-pattern) 
    //       or pattern is over (means we found matching substrings for each
    //                           sub-pattern) 

    // The following could be condensed into
    // return match && ( !end_of_string( str ) || after_asterisk );
    if ( !match )
    {
        // found non-matching sub-pattern
        return 0;
    }
    
    if ( !end_of_string( str ) )
    {
        // Trailing 
        return after_asterisk;
    }
    return 1;
}

[ysv_]

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

Согласен на все 100%.

Исправление итеративного варманта. Надеюсь последнее.
bool CompareText(const char*& s, const char*& p)
{
  while (*s!=0 && *p!=0 && *p!='*')
  {
    if (*s!=*p && *p!='?') return false;
    ++p;
    ++s;
  }
  if (*p=='*') return true;
  return (*s==0 && *p==0);
}

void SkipAsterisk(const char*&p)
{
  while (*p=='*') ++p;
}

bool FindText(const char*& s, const char*& p)
{
  const char *ss, *pp;
  while (*s!=0)
  {
    ss=s;
    pp=p;
    if (CompareText(ss, pp))
    {
      s=ss;
      p=pp;
      return true;
    }
    ++s;
  }
  return false;
}

bool PattCmp2(const char* s, const char* p)
{
  bool res=CompareText(s, p);
  if (*p!='*') return res;

  SkipAsterisk(p);
  if (*p==0) return true;
  while (*s!=0 && *p!=0)
  {
    if (!FindText(s, p)) return false;
    SkipAsterisk(p);
    if (*p==0) return true;
  }
  return (*s==0 && *p==0);
}

[npak]

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

Результат несколько великоват для постинга, поэтому я положил его по адресу http://www.ispras.ru/~npak/recursion/colormap.c

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

Приведены рекурсивная реализация и итеративная.  Обе построены на одном алгоритме.

0.  Упорядочить все вершины графа, от 1 до n.  Изначально все вершины не раскрашены.

1.  Покрасить вершину 1 в первый цвет, переходим к следующей вершине.

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

[Dimyan]

Alf, лоханулся я немножко с твоими заданиями по рекурсии :oops:
Но вот на проверку то что сделал я:

Код:

/// <summary>
		/// Удаление записи
		/// </summary>
		private void Del_Node(int NodeID)
		{
			OleDbCommand cm = new OleDbCommand("Sel_NodeType", oleDbConnection1);
			cm.CommandType = CommandType.StoredProcedure;
			OleDbParameter prmNodeID = new OleDbParameter("NodeID", OleDbType.Integer, 4);
			cm.Parameters.Add(prmNodeID);
			oleDbConnection1.Open();
			cm.Parameters["NodeID"].Value = NodeID;
			try
			{
				int i =Convert.ToInt32( cm.ExecuteScalar());
				if(i!=0)//Если тема
				{
					DialogResult result;
					result = MessageBox.Show("Вы действительно хотите удалить тему со всеми подтемами и вопросами?",
						"Удаление темы", MessageBoxButtons.YesNo, MessageBoxIcon.Question,
						MessageBoxDefaultButton.Button2);
					if(result == DialogResult.Yes)
					{
						//Ищем вложенные итемы и удаляем их
						Delete_Child(NodeID);

					}
					
				}
				else//если вопрос
				{
					DialogResult result;
					result = MessageBox.Show("Вы действительно хотите удалить вопрос?",
						"Удаление вопроса", MessageBoxButtons.YesNo, MessageBoxIcon.Question,
						MessageBoxDefaultButton.Button2);
					if(result == DialogResult.Yes)
					{
						cm.Parameters.Clear(); 
						cm = new OleDbCommand("Del_NodeName", oleDbConnection1);
						cm.CommandType = CommandType.StoredProcedure;
						
						prmNodeID = new OleDbParameter("NodeID", OleDbType.Integer, 4);
						cm.Parameters.Add(prmNodeID);
						cm.Parameters["NodeID"].Value = NodeID;
						cm.ExecuteNonQuery();												
					}

					//treeContents.SelectedNode.Remove();
					//treeContents.Invalidate();                    
				}
				
			}
			finally
			{
				oleDbConnection1.Close();
			}

			treeContents.SelectedNode.Remove();
			treeContents.Invalidate();

		}
		//*********************************************************************************************//

		private void Delete_Child(int Parent)
		{
			OleDbCommand cm = new OleDbCommand("Sel_Child", oleDbConnection1);
			cm.CommandType = CommandType.StoredProcedure;
			OleDbParameter prmParentID = new OleDbParameter("ParentID", OleDbType.Integer, 4);
			cm.Parameters.Add(prmParentID);
		
			cm.Parameters["ParentID"].Value = Parent;

			
			while(Convert.ToBoolean(cm.ExecuteScalar()))//Есть еще дети
			{
				Delete_Child(Convert.ToInt32( cm.ExecuteScalar()));
			}

			cm.Parameters.Clear(); 
			cm = new OleDbCommand("Del_NodeName", oleDbConnection1);
			cm.CommandType = CommandType.StoredProcedure;
						
			prmParentID = new OleDbParameter("NodeID", OleDbType.Integer, 4);
			cm.Parameters.Add(prmParentID);
			cm.Parameters["NodeID"].Value = Parent;
			cm.ExecuteNonQuery();	
            
		}

Это функция уделения всех потомков узла из базы при удалении его из TreeView из уже известной тебе программы.
Помоему довольно длинно но работает, это все что я смог прибумать

[Finch]

Alf, область, где бы я не рекомендовал использовать рекурсию, это обработка больших динамических массивов. Программа работает крайне нестабильно. Вопрос об увелечении стека, это вопрос времени. Всегда можно найти длину массива, при которой программа будет вылетать. Столкнулся я с этим, когда мне нужно было сортировать сверхбольшие массивы (около миллиона элементов) с сверхбольшими числами (32 байта). Алгоритм который заложен в стандартную библиотеку борланда вылетал на массиве чуть больше тысячи. Пришлось брать битовую сортировку. После этого я понял поговорку. Рекурсией программируют только боги. Потому что только у богов есть компьютеры с неограниченными ресурсами. Статья мне понравилась. А то что было сказано выше, это так камень в огород.
Насчет раскраски стран, я не до конца понял. Возьми Россию. Со сколькими странами она граничит. Я думаю, что больше четырех.

[Alf]

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

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

Программа работает крайне нестабильно.

Я нестабильные программы и через итерацию писать умею. Обращайтесь, научу  
Что лишний раз подтверждает тезис об эквивалентности рекурсии и итерации...

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

См. предыдущий пункт.

Столкнулся я с этим, когда мне нужно было сортировать сверхбольшие массивы (около миллиона элементов) с сверхбольшими числами (32 байта). Алгоритм который заложен в стандартную библиотеку борланда вылетал на массиве чуть больше тысячи.

Странно, я об этой фирме был лучшего мнения... Хоть и по большей части заочно, ибо уже несколько лет не работаю с их компиляторами.

Пришлось брать битовую сортировку.

Думаю, что объем оперативной памяти, необходимый для размещения такой структуры (32 Мб), по нынешним меркам все же не настолько велик, чтобы считать такой массив "сверхбольшим" и прибегать к каким-то особо изощренным методам сортировки. Сейчас, наверное, уже и в принципе невозможно купить компьютер с объемом памяти менее 128 Мб, а в таком объеме подобный массив уместится. Разве что эта задача много лет назад решалась, когда еще персоналки поскромнее были.
Если бы объемы сортируемых данных заведомо превышали объем доступной оперативной памяти, тогда имело бы смысл прибегнуть к одному из методов внешней сортировки.
Тем не менее сортировка и поиск, пожалуй, являются одними из наиболее (если не самыми) теоретически и практически проработанными вопросами информатики, взять хотя бы сооответствующий том Кнута размером и весом с хороший кирпич. Так что тут вряд ли имеет смысл изобретать велосипед. Даже если это чрезвычайно элегантный рекурсивный велосипед.

После этого я понял поговорку. Рекурсией программируют только боги. Потому что только у богов есть компьютеры с неограниченными ресурсами.

У богов и задачи посложнее, чем сортировка массивов, пусть даже супермассивов  

Статья мне понравилась.

Спасибо. Обещаю, что скоро будут еще в развитие этой темы.

...Насчет раскраски стран, я не до конца понял. Возьми Россию. Со сколькими странами она граничит. Я думаю, что больше четырех.

Честно говоря, немного не понял вопроса (или утверждения).
Теорема о четырех красках вовсе не утверждает, что на свете не существует государств с более чем четырьмя соседями  
Она утверждает всего лишь , что любую плоскую географическую карту можно раскрасить таким образом, что никакие две области, имеющие общую границу, не будут иметь один и тот же цвет, и при этом обойтись четырьмя красками (если карта достаточно простая, то возможно и меньшее количество, 4 - это верхний предел). Это доказано теоретически и неоднократно проверено на практике (я и сам когда-то давал эту задачу в качестве упражнения студентам, изучающим Pascal, и большинство справлялось успешно).
Кстати, npak решил эту задачу и выложил ее решение (см. выше). Честно говоря, я его еще не смотрел (сейчас у меня цейтнот, и пришлось вообще забросить эту ветку форума, хотя мне весьма нравится завязавшаяся здесь дискуссия), но обязательно вернусь к ней в ближайшем времени.

[npak]

Finch, да, рекурсия -- не универсальный метод.

У неё есть ограничения.  Наиболее существенное -- возможность переполнения стека.  Это может быть вызвано слишком медленным понижением сложности задачи, при относительно большой начальной сложности.

Например, для быстрой сортировки на каждом шаге рекурсии сложность задачи понижается примерно в два раза (массив, который нужно отсортировать, делится примерно пополам).  В среднем глубина рекурсии при сортировке массива длиной n нужна примерно lg2(n) глубина рекурсии.  Но возможны такие начальные значения в массиве, что на каждом шаге сложность понижается на 1 (например, массив отсортирован в обратном порядке).  Для сортировки такого массива длиной n потребуется глубина рекурсии порядка n.

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

Теперь про раскраску карты.  Надо раскрасить карту так, чтобы соседние страны были раскрашены разными цветами.

[Finch]

Alf писал(а):

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

Я не думаю, что такой изошренный. Алгоритм хорошо описывается в третьем томе Кнута. После алгоритма, который применили в Борланде. Эти два алгоритма считаются одними из самых быстрых. Когда я написал сортировку по битовому алгоритму с применением рекурсии. Он также стабильно вылетал на массиве, чуть больше 1000. И вопрос, как часто ты сортируеш массивы даных с длиной больше миллиона? Это  был мой первый опыт. И после этого я больше этим не занимался. Зато приобрел опыт и дополнительную функцию в мою коллекцию.

npak В том то и дело, что массив был равно распределен.

[npak]

Finch, что значит "вылетал"?  В чём это проявлялось?

У меня нет сейчас под рукой Кнута, а припомнить битовую сортировку не могу  :oops: .  Напомни, пожалуйста, в чём особенность алгоритма?

Какой продукт Борланда ты использовал в своей работе, на какой операционной системе?

[Finch]

npak,  было переполнение стека. Хотя я этого не ожидал. и не предпологал.
Алгоритм по своей идее очень простой. Надо начинать со старших битов.
1. в масиве все числа которые имеют соответствующий бит равный 1 сносятся наверх, которые имеют бит равный 0 сносятся вниз.
2. Получается массив разбит на две части: Первая часть где все числа имеют соответствующий бит 1, Вторая часть где все числа имеют соответствующий бит 0.
3. Выполняется операция 1 для каждой части с понижением значимости бита, до тех пор пока не дойдем до самого младшего бита.
Естественно делается ловушка, если в массиве всего один член.

Количество просмотров всего массива зависит только от количества бит в числе. Недостаток этого алгоритма, только в том, что его надо настраивать на данные (по моему мнению).
Реализовал его я тоже просто. Есть два бегунка. Один идет сверху второй снизу. Когда верхний бегунок находит число у которого соответсвующий бит равен 0 он останавливается. Нижний соответственно для бита равного 1. Когда два бегунка остановились программа производит обмен между ячейками. И запускает бегунки. До тех пор пока бегунки не встретятся.
Все. что описано выше это для сортировки младшие внизу, старщие наверху.
Когда я это писал, то работал в Delphi 4.5 Win98. Сейчас у меня стоят Borland C++ 5.0 Builder, Delphi 4.5,  WinXP. На новые версии не хочу переходить. Мне этого вполне достаточно (привычка это очень плохое дело ).

[npak]

Finch,

 Хороший рекурсивный алгоритм с гарантированной глубиной рекурсии (256 (8*32) в твоём случае).  Можно предложить Alf'у взять в качестве примера для статьи о рекурсии.

[NetRaider]

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

Категорически не соглашусь: для многих вариантов сортировок разрыв между верхней и нижней границ оценок производительности очень высок, тот же quckSort может давать до O(n^2) сравнений. Можно вспомнить еще различные комбинации сетей сортировок, например оптимальными для параллельной работы, для которых не существует нормального алгоритма построения. В том же 3-ем томе Кнута 50-ти бальных задач(которые являются научными проблемами), в главах о сортировке больше всего. До сих пор неизвестна зависимость минимального кол-ва сравнений от кол-ва элементов. Да и видов сортировки существует горааздо больше, чем думают.  Вообще проблема сложности алгоритмов(и не только сортировки) в информатике стоит очень остро. Так что здесь есть над чем думать...

[Alf]

Категорически не соглашусь: для многих вариантов сортировок разрыв между верхней и нижней границ оценок производительности очень высок, тот же quckSort может давать до O(n^2) сравнений. Можно вспомнить еще различные комбинации сетей сортировок, например оптимальными для параллельной работы, для которых не существует нормального алгоритма построения. В том же 3-ем томе Кнута 50-ти бальных задач(которые являются научными проблемами), в главах о сортировке больше всего.

Давайте все-таки попробуем отделить проблемы, связанные с действительной сложностью задачи, от проблем некорректной реализации. Одно дело - задача, для которой нет алгоритма в принципе (кстати, а как ее в таком случае решать программно?). Совсем другое дело - неподходящая реализация работающего алгоритма, переполняющая стек. Я бы не спешил относить это к научным проблемам.
Тем более что npak предлагает рекурсивный вариант с гарантированно ограниченной глубиной, лишний раз подтверждая, что все гениальное просто. Хотя это нужно уж очень любить рекурсию, чтобы даже массивы сортировать с ее применением. Лично я бы все же воздержался от рекурсии в пользу итерации, да простят мне мои низменные пристрастия.

До сих пор неизвестна зависимость минимального кол-ва сравнений от кол-ва элементов.

Таки неизвестна ни для какого алгоритма? Или речь идет все же об отдельных особо сложных случаях?

Да и видов сортировки существует горааздо больше, чем думают.

В этом и беда. Те виды, над которыми не думают, и вызывают проблемы.

Так что здесь есть над чем думать...

Вот с этим не могу не согласиться.

[NetRaider]

Давайте все-таки попробуем отделить проблемы, связанные с действительной сложностью задачи, от проблем некорректной реализации. Одно дело - задача, для которой нет алгоритма в принципе (кстати, а как ее в таком случае решать программно?). Совсем другое дело - неподходящая реализация работающего алгоритма, переполняющая стек. Я бы не спешил относить это к научным проблемам.
Тем более что npak предлагает рекурсивный вариант с гарантированно ограниченной глубиной, лишний раз подтверждая, что все гениальное просто. Хотя это нужно уж очень любить рекурсию, чтобы даже массивы сортировать с ее применением. Лично я бы все же воздержался от рекурсии в пользу итерации, да простят мне мои низменные пристрастия.

С этим я согласен, просто меня задела фраза о том что сортировка и поиск являются проработанными вопросами. Задел за живое, так сказать...  

До сих пор неизвестна зависимость минимального кол-ва сравнений от кол-ва элементов.

Таки неизвестна ни для какого алгоритма? Или речь идет все же об отдельных особо сложных случаях?
[/quote]
Ты не понял...
Минимальное кол-во сравнений для n элементов неизвестно(без привязки к конкретному алгоритму). Например для сортировки 3 элементов нужно минимум 3 сравнения, для 4 - 5, 5-7, для n больше 8 кол-во сравнений незвестно... А зная эту зависимость можно намного точнее определить производительность различных алгоритмов.

[npak]

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

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

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

Хотя это нужно уж очень любить рекурсию, чтобы даже массивы сортировать с ее применением.

Интересно, что вы используете для сортировки массивов?

[Alf]

Ты не понял...
Минимальное кол-во сравнений для n элементов неизвестно(без привязки к конкретному алгоритму). Например для сортировки 3 элементов нужно минимум 3 сравнения, для 4 - 5, 5-7, для n больше 8 кол-во сравнений незвестно... А зная эту зависимость можно намного точнее определить производительность различных алгоритмов.

Кнута под рукой нет, попался Вирт. Открываю главу "Сортировка массивов", читаю:

Анализ сортировки простыми включениями. Общее число сравнений C и пересылок M:
Cmin=n-1
Cavg=1/4(n^2+n-2)
Cmax=1/2(n^2+n)-1
... и т.д.

Анализ сортировки простым выбором. Число сравнений ключей C не зависит от начального порядка ключей.
C=1/2(n^2-n)

Или я неверно понял постановку вопроса?

P.S. В случае массива из 3-х элементов вовсе не обязательно нужны 3 сравнения. Если известно, что A>B и B>C, столь ли необходимо сравнивать A и C? Я бы не стал говорить, что 3 - это минимум.

[Alf]

Алгоритм битовой сортировки предлагает Кнут, а не я

Хорошо, пускай будет так: Кнут предлагает, а npak продвигает в массы  

Интересно, что вы используете для сортировки массивов?

Мне даже неловко признаться, что я оказался как-то в стороне от этой проблемы, вроде как отщепенцем себя чувствую  

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

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

[NetRaider]

Кнута под рукой нет, попался Вирт. Открываю главу "Сортировка массивов", читаю:

Анализ сортировки простыми включениями. Общее число сравнений C и пересылок M:
Cmin=n-1
Cavg=1/4(n^2+n-2)
Cmax=1/2(n^2+n)-1
... и т.д.

Анализ сортировки простым выбором. Число сравнений ключей C не зависит от начального порядка ключей.
C=1/2(n^2-n)

Это для конкретного алгоритма...

P.S. В случае массива из 3-х элементов вовсе не обязательно нужны 3 сравнения. Если известно, что A>B и B>C, столь ли необходимо сравнивать A и C? Я бы не стал говорить, что 3 - это минимум.

А если в результате сравнения окажется что B<C ?  3 - это гарантируемый минумум сравнений. Естественно что может потребоваться и меньше сравнений. Но минимальный максимум - 3.

[npak]

NetRaider, есть алгоритмы сортировки, в которых вообще нет сравнений.

Пример -- сортировка целых чисел массивом.  Проводится в предположениях, что числа, которые надо отсортировать, в диапазоне [p, q]

Тогда заводится битовый массив размером (q-p+1), все биты обнулены.

Сортировка.  Перебираем целые числа одно за другим.  Встретив число n выставляем бит (флаг) в ячейке с номером (n-p) (нумеруем битовый массив с нуля)

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

Можно рассмотреть вместо битов счётчики.  Для каждого числа в исходном массиве считаем, сколько раз число встретилось, затем столько раз это число сбрасываем в результат

Как видно, вообще ни одного сравнения не производится.

Так что минимальное число сравнений -- 0.

[npak]

Alf, минимальный максимум строится так.

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

Правда, не совсем понятно, какое отношение эта конструкция имеет к сортировке?  Максимумы чего строятся на первом шаге?

[Alf]

npak, минимаксы из теории принятия решений, теории игр (AB-деревья и др.) и тому подобные к теории NetRaider'а я тут никоим боком прилепить не сумел. Из каких альтернатив мы выбираем минимакс?

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

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

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

[NetRaider]

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

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

Да и в чем тогда необходимость изобретения разных алгоритмов, если метрики у них все равно одинаковы?

Это зависит от природы используемых данных и начальных условий(приминительно к алгоритмам сортировки). Например, нужно отсортировать массив объектов; берем быструю сортировку - быстродействие в худшем случае O(n^2), для любых объектов подойдет. Но если исходный массив состоит из чисел, время можно улучшить до O(n).

...Но минимальный максимум - 3.

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

Ок, берем несколько алгоритмов сортировки(рассматриваем кол-во k(n)сравнений в наихудшем случае, т.е. максимумы)
1) быстрая - k(n) = n^2
2) сортировка простым выбором - k(n) = 1/2(n^2-n)
3) для наглядности можно взять какой-нибудь 'страшный'  алгоритм -   k(n) = n^3
4) 'несуществующий' алгоритм -  пусть нам известна формула для минимального кол-ва сравнений(о которой я говорил) и алгоритм ее реализующий.  k(n) = c(n) =

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

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

1) - 25
2) - 10
3) - 125
4) формула неизвестна, но 5 объектов можно отсортировать за 7 сревнений.

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

P.S. Неудачно выбрал термин...

[NetRaider]

NetRaider, есть алгоритмы сортировки, в которых вообще нет сравнений.

Это мне известно. Все вышесказанное применимо для множеств с определенными отношениями порядка ('>', '<', и возможно '=') и никакими другими. Если доступны другие операции над элементами множества, тогда сортировка вырождается в частные случаи(например для чисел).

[Alf]

Тема рекурсии возрождается.

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

Обсуждаем здесь или делаем новую тему?

[npak]

Alf, я начал тему здесь:
https://forum.shelek.ru/index.php/topic,4189.0.html

[Olegator]

Вот здесь небольшая ошибка
https://club.shelek.ru/viewart.php?id=184

, в которых применение рекурсии просто расточительно и е выдерживает никакой конкуренции с рекурсией.

В принципе всё понятно. Но лучше исправить.

, в которых применение рекурсии просто расточительно и не выдерживает никакой конкуренции с итерацией.

[RXL]

Действительно, не логично выходит. Тут явная описка.
Да простит меня Alf, я исправил этот текст.

[Alf]

Спасибо обоим. Странно, что никто раньше не заметил.