Рекурсия в математике

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

Maslov в сообщении #258009 писал(а):

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

Хотелось бы более подробно раскрыть, что здесь понимается под большей эффективностью. Одно дело, если итерационный алгоритм требует на порядок меньше операций (или даже рекурсивный алгоритм требует $f(n)$ операций, итерационный $g(n)$ операций и $g(n)/f(n) \to 0$ при $n \to \infty$). А другое дело, если итерационный алгоритм даёт выигрыш в конкретное число операций, не зависящее от $n$ (или даже растущее с ростом $n$, но гораздо медленнее, чем общее число операций). В последнем случае выигрыш несущественен.

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

[Maslov]

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

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

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

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

Maslov в сообщении #258027 писал(а):

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

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

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

Там это тоже не раскрывается. Просто идёт речь про какую-то абстрактную "большую эффективность" и всё.

[Maslov]

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

Там это тоже не раскрывается. Просто идёт речь про какую-то абстрактную "большую эффективность" и всё.

В той теме было одно замечание Бодигрим'а на тему ассимптотической сложности:

Бодигрим в сообщении #255532 писал(а):

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

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

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

Если эмулировать стек, то это будет не выигрыш, а проигрыш по времени. А с точки зрения теории так вообще не важно, что там у нас: стек или эмуляция стека

Я в той теме уже задачку кинул, кину и сюда. Для функции Аккермана программа на Паскале (другими языками не владею, простите) выглядит так (тип natural --- это тип для произвольного натурального числа, натуральный ряд начинаем с нуля ):

function A(z,x,y: natural): natural;
begin
if z = 0 then A := x + y else
  if y = 0 then A := sign(z-1) else
    A := A(z-1,x,A(z,x,y-1))
end;

Коротко и предельно ясно! А теперь попробуйте написать вычисление функции $A$ без рекурсивного вызова У меня несколько лет назад один студент на курсе это сделал, так я до сих пор нахожусь под впечатлением от его подвига

[feag]

По теме:
Посмотрите Рекурсивный анализ Гудстейна, там много примеров.