Удаление рекурсии - заглянуть в закулисную теорию

10

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

Итак, я знаю, что у каждой рекурсивной программы есть итеративный аналог, и я вроде как понимаю популярное объяснение, которое предлагается для нее, поддерживая что-то похожее на «системный стек» и выдвигая настройки среды, такие как адрес возврата и т. Д. Я нахожу этот вид волнистым ,

Будучи немного более конкретным, я хотел бы (формально) посмотреть, как можно доказать это утверждение в тех случаях, когда у вас есть функция, вызывающая цепочку . Кроме того, что если существуют некоторые условные операторы, которые могут привести к вызову некоторого ? То есть граф вызовов потенциальных функций имеет несколько сильно связанных компонент. $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$ $F_i$ $F_j$

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

Что я действительно спрашиваю, так это вопроса $2$

(1) Есть ли действительно более формальное (убедительное?) Доказательство того, что рекурсия может быть преобразована в итерацию?

(2) Если эта теория действительно существует, то почему я нахожу, например, итерацию предзаказа проще, а поступорядочения так сложно? (кроме моего ограниченного интеллекта)

pl.programming-languages recursion recursive Итачи Учиха
источник

1

как слово, повторяющееся :)

Акаш Кумар

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

singhsumit

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

Рафаэль

Спасибо всем за ваши комментарии - думаю, у меня есть кое-что почитать.

Итачи Учиха

@Raphael - Один комментарий о том, почему я думаю, что итерация пост-заказа трудна (кроме того, что я не могу этого сделать). Я читал несколько статей об удалении рекурсии и столкнулся с тем, что называется хвостовой рекурсивной функцией. Оказывается, их легче итерировать. Я все еще формально не понимаю, почему это правда; но есть еще одна вещь, которую я должен добавить. Я слышал, что итеративный заказ требует двух стеков, а не одного, но не знаю деталей. И теперь я потерялся - почему эта разница между этими двумя режимами обхода? И почему рекурсия хвоста проста в обращении?

Итачи Учиха

6

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

$F \to F_1 \to \dots \to F_n \to F$ $F_1, \dots, F_n$ $F$

$F_j$ $F$ $F_j \to \dots \to F \to \dots \to F_j$

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

с f'и g'нерекурсивных функций (или, по крайней мере, независимо от fи g) становится

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Это естественно распространяется на большее количество функций и более сложные функции.

Рафаэль
источник

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

Рафаэль

1

Рафель, твой трюк работает только тогда, когда обе рекурсивные функции принимают аргументы одного типа. Если fи gпринимать различные типы типов, требуется более общий прием.

Андрей Бауэр

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

Итачи Учиха

fg

n - 1

$n-1$

n - 2

$n-2$

Ну, смотрите мой ответ о том, как это сделать.

Андрей Бауэр

8

Да, есть убедительные основания полагать, что рекурсия может быть превращена в итерацию. Это то, что делает каждый компилятор, когда переводит исходный код на машинный язык. Для теории вы должны следовать советам Дейва Кларка. Если вы хотите увидеть реальный код, который преобразует рекурсию в нерекурсивный код, взгляните на machine.mlязык MiniML в моем PL Zoo (обратите внимание, что loopфункция внизу, которая фактически выполняет код, является хвостовой рекурсивной, и поэтому она может быть тривиально преобразован в реальный цикл).

Еще кое-что. MiniML не поддерживает взаимно рекурсивные функции. Но это не проблема. Если у вас есть взаимная рекурсия между функциями

f_{1} : A_{1} \to B_{1}

$f_1 : A_1 \to B_1$

f_{2} : A_{2} \to B_{2}

$f_2 : A_2 \to B_2$

⋮

$\vdots$

f_{n} : A_{n} \to B_{n}

$f_n : A_n \to B_n$

рекурсия может быть выражена в виде одной рекурсивной карты

f : A_{1} + \dots + A_{n} \to B_{1} + \dots + B_{n},

$f : A_1 + \cdots + A_n \to B_1 + \cdots + B_n,$

Андрей Бауэр
источник

8

Вы можете посмотреть на SECD-машину . Функциональный язык (хотя это может быть любой язык) переводится в серию инструкций, которые управляют такими вещами, как помещение аргументов стеков, «вызов» новых функций и т. Д., Управляемых простым циклом.
Рекурсивные вызовы никогда не выполняются. Вместо этого инструкции тела вызываемой функции помещаются в стек для запуска.

Связанный подход - машина CEK .

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

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

Дэйв Кларк
источник

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

Итачи Учиха

[cntd] Я имею в виду, что мне понравится доказательство, если оно есть, чтобы сказать мне, почему итерация одной программы проще, чем другой. Но в некотором смысле рекурсивный в итеративный преобразователь должен работать независимо от того, какую рекурсивную программу он использует в качестве входных данных. Не уверен, но я думаю, что создание такого конвертера может быть столь же сложным, как и проблема остановки? Я просто догадываюсь здесь - но мне бы хотелось, чтобы существовал рекурсивный итеративный преобразователь, и если это произойдет, я хотел бы объяснить внутреннюю сложность итерации различных рекурсивных программ. Я не уверен, но я должен отредактировать вопрос? Мой вопрос понятен?

Итачи Учиха

@ItachiUchiha - я не думаю, что ваша проблема неразрешима. Посмотрите на ответ Андрея Бауэра. Он отмечает, что каждый компилятор делает это, когда переводит исходный код на машинный язык. Также он добавляет, что вы можете увидеть реальный код, который преобразует рекурсивный в нерекурсивный язык MiniM (a) l. Это ясно указывает на то, что существует процедура принятия решения для «итерации» рекурсии. Я не уверен в присущей (концептуальной) сложности / сложности удаления рекурсии. Я не очень четко понимаю этот вопрос, но он выглядит интересно. Может быть, вы можете отредактировать свой вопрос, чтобы получить лучший ответ

Акаш Кумар

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

Дейв Кларк

6

В : «Есть ли действительно более формальное (убедительное?) Доказательство того, что рекурсия может быть преобразована в итерацию?»

A : Полнота Тьюринга машины Тьюринга :-)

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

Я думаю, что вы можете найти много статей / статей о « рекурсивном и итеративном преобразовании » (см. Ответ Дейва или просто Google ключевые слова), но, возможно, менее известным (и практичным ) подходом является последнее исследование аппаратной реализации рекурсивных алгоритмов ( использование языка VHDL, который «скомпилирован» непосредственно в аппаратную часть). Например, см. Статью В. Склярова « Рекурсивные алгоритмы на основе ПЛИС » ( В статье предлагается новый метод реализации рекурсивных алгоритмов в аппаратном обеспечении. Изучено два практических применения рекурсивных алгоритмов в области сортировки и сжатия данных. подробно .... ).

Марцио де Биаси
источник

1

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

Преобразование CPS тесно связано с явным хранением стека вызовов в традиционном стеке на основе массива, но вместо массива стек вызовов представлен связанными замыканиями.

Жюль
источник

0

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

Как указывалось в статье Питера Лэндена 1965 года «Соответствие между ALGOL 60 и лямбда-нотацией Черча», последовательные процедурные языки программирования можно понимать в терминах лямбда-исчисления, которое обеспечивает основные механизмы для процедурной абстракции и применения процедур (подпрограмм).

большая часть этой статьи находится на этой странице википедии, посвященной церковному тезису . Я не уверен в точных деталях, но статья в Википедии, кажется, указывает, что именно Россер (1939) первым доказал эту эквивалентность между лямбда-исчислением и машинами Тьюринга. возможно / предположительно его статья имеет стековый механизм для преобразования (возможно, рекурсивных) лямбда-вызовов в конструкцию tm?

Россер, JB (1939). «Неформальное изложение доказательств теоремы Годеля и теоремы Чёрча». Журнал символической логики (Журнал символической логики, том 4, № 2) 4 (2): 53–60. DOI: 10.2307 / 2269059. JSTOR 2269059.

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

ВЗН
источник

1

Доказательство эквивалентности по Тьюрингу и лямбде приведено в приложении к этому документу: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Раду ГРИГОР,

Удаление рекурсии - заглянуть в закулисную теорию

Ответы: