Задачки на рекурсию.

[Профессор Снэйп]

Nik_Svan в сообщении #258748 писал(а):

Зря вы так. Если Маслов вас затянет на свою территорию, то вы не сможете ответить и на совсем элементарные вопросы.

А мне господин Maslov показался значительно грамотнее Вас. Вы только в фекальных темах хорошо разбираетесь.

-- Пт ноя 06, 2009 06:56:41 --

venco в сообщении #258758 писал(а):

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

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

[Xaositect]

Профессор Снэйп в сообщении #258836 писал(а):

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

Если рекурсию выискивать, то она точно везде будет. В конце концов раздел математики, изучающий вычислимые функции, называется часто Recursion theory.

А вообще над определением нерекурсивного алгоритма можно подумать. Вот, скажем, вычисление полинома от аргументов или схему примитивной рекурсии, в которой базовые функции являются полиномами, я бы все-таки назвал нерекурсивным алгоритмом (сюда попадают очевидные циклы for для $2^n$, $n!$, $2^{2^n}$ и еще много чего). Но это достаточно узкий класс. Кажется мне, что я где-то видел какую-то иерархию примитивно-рекурсивных функций, где было что-то похожее, надо Роджерса и Одифредди полистать на досуге.

[Профессор Снэйп]

Xaositect в сообщении #258837 писал(а):

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

В Роджерсе точно ничего подобного нет. За Одифредди отвечать не буду, всю книгу не помню.

А иерархию одну, в которой участвуют примитивно-рекурсивные функции, я таки знаю. Если мы берём примитивно-рекурсивные перестановки и начинаем порождать ими подгруппу в группе перестановок, то, в конечном счёте, получается группа всех рекурсивных перестановок. Более того, любая рекурсивная перестановка $f$ может быть представлена в виде $g_1 \circ g_2^{-1} \circ g_3 \circ g_4^{-1} \circ g_5 \circ g_6^{-1}$, где $g_1, \ldots, g_6$ --- примитивно-рекурсивные перестановки. Меньшим чем $6$ числом примитивно-рекурсивных перестановок породить произвольную рекурсивную перестановку
не удастся. Более того, класс композиций из четырёх примитивно-рекурсивных перестановок является собственным подклассом класса композиций из пяти примитивно-рекурсивных перестановок и и. д. Отсюда иерархия.

Сами примитивно-рекурсивные функции можно упорядочивать, например, по сложности вычислений (это естественная иерархия, годится для произвольного класса вычислимых функций). Можно сделать, например, так: примитивно-рекурсивные функции --- это, в точности, функции, время вычисления которых ограничено уровнями функции Аккермана. Вот эти уровни и делать классами иерархии

Xaositect в сообщении #258837 писал(а):

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

Даже терминология против Вас

[Nik_Svan]

Профессор Снэйп писал(а):

А мне господин Maslov показался значительно грамотнее Вас.

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

Профессор Снэйп писал(а):

Вы только в фекальных темах хорошо разбираетесь.

Я не виноват, что из этих фекалиев ваша профессорская голова произростает.

[Xaositect]

Профессор Снэйп в сообщении #258838 писал(а):

Даже терминология против Вас

А я говорю, все рекурсия, если копнуть.
Но вот циклы for, полученные из такой рекурсии, все-таки не вызывают подозрения. Или Вы скажете,. что счетчик цикла - это модель стека?

[Профессор Снэйп]

Xaositect в сообщении #258974 писал(а):

Профессор Снэйп в сообщении #258838 писал(а):

Даже терминология против Вас

А я говорю, все рекурсия, если копнуть.
Но вот циклы for, полученные из такой рекурсии, все-таки не вызывают подозрения. Или Вы скажете,. что счетчик цикла - это модель стека?

Сам по себе счётчик --- нет, конечно, не модель. Но ведь внутри стека идёт работа с какими-то другими данными, не только со счётчиком...

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

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

Нерекурсивным, по сути, будет только вычисление полиномов. Факториалы и степени уже рекурсивны.

-- Пт ноя 06, 2009 17:20:28 --

Nik_Svan в сообщении #258966 писал(а):

Я не виноват, что из этих фекалиев ваша профессорская голова произростает.

Кто как обзывается, тот сам так называется.

[Nik_Svan]

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

[cepesh]

Nik_Svan забанен на 2 месяца за многократное нарушение правил.

[Профессор Снэйп]

Xaositect в сообщении #258837 писал(а):

Вот, скажем, вычисление полинома от аргументов или схему примитивной рекурсии, в которой базовые функции являются полиномами, я бы все-таки назвал нерекурсивным алгоритмом (сюда попадают очевидные циклы for для $2^n$, $n!$, $2^{2^n}$ и еще много чего). Но это достаточно узкий класс.

Почему узкий? Разве туда все примитивно-рекурсивные функции не войдут?

[Xaositect]

Профессор Снэйп в сообщении #259030 писал(а):

Почему узкий? Разве туда все примитивно-рекурсивные функции не войдут?

В том виде, как это у меня написано, туда не войдет ничего больше $a^{b^n}$, вроде бы.
А если замыкание по суперпозиции рассмотреть, то не уверен.

[Профессор Снэйп]

Xaositect в сообщении #259107 писал(а):

Профессор Снэйп в сообщении #259030 писал(а):

Почему узкий? Разве туда все примитивно-рекурсивные функции не войдут?

В том виде, как это у меня написано, туда не войдет ничего больше $a^{b^n}$, вроде бы.
А если замыкание по суперпозиции рассмотреть, то не уверен.

Если по суперпозиции замыкать, то войдут степени с любым количеством этажей. А по суперпозиции замыкать, безусловно, надо: это самый далёкий от рекурсии оператор. Куда же без неё.

Напомню, что функция называется примитивно рекурсивной, если её можно породить из базисных (ноль, прибавление единицы и проекции --- совсем простые функции) суперпозициями и примитивными рекурсиями. Суперпозиция точно рекурсию не использует. Если Вы хотите считать, что примитивная рекурсия на самом деле никакая не рекурсия, то у Вас и получится, что все примитивно рекурсивные функции можно вычислить без рекурсии

[Xaositect]

Да, получается так. Жаль.

[Профессор Снэйп]

На самом деле, если разобраться, то минимизация тоже рекурсию не использует.

Примем следующее обозначение: $\bar{x} = x_1, \ldots, x_k$.

Пусть $f(\bar{x}) = \mu y(g(\bar{x},y)=0)$. Тогда если у нас есть процедура, вычисляющая $g$, то процедура вычисления $f$ выглядит следующим образом:

Используется синтаксис Pascal

function f(x_1,...,x_k: integer): integer;
var i: integer;
begin
  i := 0;
  while g(x_1,...,x_k,i) <> 0 do inc(i);
  f := i
end

Вроде никакой рекурсии не наблюдается. А ведь есть теорема о том, что любая частично рекурсивная функция $f$ представима в виде

$$ f(\bar{x}) = h(\mu y(g(\bar{x},y)=0)) $$

где функции $h$ и $g$ примитивно рекурсивны. То есть любую вычислимую функцию можно вычислить без рекурсии

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