рекурсивная => нерекурсивная реализация

Tail и не-tail очень разные, как минимум нужно определить нужен стек или нет, потому и алгоритмы будут разные.

к итерации можно привести все ф-и, которые являются общерекурсивными (и некоторые частично-рекурсивные, наверное)

не возвращаемся сюда пока не освоим хотя бы базовые понятия теории гёделя.

не возвращаемся сюда пока не освоим хотя бы базовые понятия теории гёделя.

теории гёделя.

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

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

взаимно :)

почему же ты, утверждая что знаешь ответ на вопрос тс-а, не приводишь его?

взаимно :)

Я и не использую.

почему же ты, утверждая что знаешь ответ на вопрос тс-а, не приводишь его?

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

Я и не использую.

сомневаюсь.

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

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

Интересно...

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

То есть, вообще низзя.

сомневаюсь.

Зря.

существую невычислимые частично-рекурсивные функции.

Нет, не существуют. Потому что «частично-рекурсивная функция» и «вычислимая функция» - синонимы.

ты же грозился привести любую вычислимую (множество общерекурсивных функций совпадает с множеством вычислимых — см тезис чёрча-тьюринга

Общерекурсивные ф-и - подмножество частично-рекурсивных. В частности, все общерекурсивные функции останавливаются.

начни пруфец, пожалуй, с аккермана.

ф-я Аккермана - частично-рекурсивная, но не общерекурсивная. Я вижу, что ты читал статью в википедии, но это было давно. Перечитай.

Для примитивно (и обще) рекурсивных - можно.

не общерекурсивная

не примитивно-рекурсивная офк

Ты не понял. Твое утверждение противоречиво. Еще раз

любая примитивно рекурсивная функция является частично рекурсивной

Кроме того:

Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических причин и по сути являются результатом неточного перевода английских терминов partial recursive function и total recursive function, которые по смыслу более правильно переводить как «рекурсивные функции, определенные на части множества возможных аргументов» и «рекурсивные функции, определенные на всём множестве возможных аргументов»

что же мешает ф-ции, определенной на всем множестве быть переписанной в итеративный вид? Я например, не вижу препятствий.

на всем

на части множества //fixed

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

В частности, все общерекурсивные функции останавливаются.

молодец. осталась самая малость: научиться делать логические выводы. на этот раз я сделаю это за тебя: ... и поэтому являются вычислимыми по тьюрингу :)

ф-я Аккермана - частично-рекурсивная, но не общерекурсивная.

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

потому что не у всех уравнений есть корни в рассматриваемом поле?

Ты не понял. Твое утверждение противоречиво.

Где оно противоречиво? Примитивно-рекурсивная функция является частинчо-рекурсивной, но не наоборот. По-этому если что-то верно для примитивно-рекурсивной ф-и - это не значит, что оно верно для частично-рекурсивных.

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

Я например, не вижу препятствий.

Если ф-я частично-рекурсивна то она может потреблять потенциально бесконечное количество памятидля данных аргументов (то есть потребление памяти невычислимо). Если ф-я примитивно-рекурсивная - то только фиксированное (потребление памяти вычислимо).

Интересно...

Только неверно.

То есть, вообще низзя.

Да, компиляторы не существуют.

молодец. осталась самая малость: научиться делать логические выводы. на этот раз я сделаю это за тебя: ... и поэтому являются вычислимыми по тьюрингу :)

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

ты лжёшь.

Нет, просто опечатка. Я ее сразу же и поправил в непосредственно следующем посте.

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

Не силен в математике, но я вообще, честно говоря не понял даже значения «определенные на части множества возможных аргументов» Сначала создай подмножество из множества возможных аргументов, а затем вычисляй уже на этом подмножестве, и у тебя будет уже «определенные на всём множестве возможных аргументов» А смысл тот же самый.

Демагогия какая то...

Заходи, третьим будешь. Мы тут уже которую страницу пытаемся ровно это же объяснить.

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

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

Лол, anonimous снова думает, что в чем-то разобрался.

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

Если дампать в стек

функция которая использует стек (в любом виде) - рекурсивная. Не важно, в каком виде ты рекурсию _записываешь_ - либо в виде func(x), явно, либо в виде набора примитивных инструкций push/call/jmp/pop/ret - процесс остается рекурсивным. Вопрос в том можно ли из рекурсивного процесс сделать нерекурсивный, например как тут:

1:
fact 0 = 1
fact n = n*fact(n-1) 
//рекурсивный процесс, можно переписать в CPS завелосипедить свой стек и т.п. - эти трансформации можно сделать автоматически и убирают явную рекурсию, но процесс остается рекурсивным

2:
fact 0 acc = acc
fact n acc = fact (n-1) (n*acc)
//итерационный процесс, хоть и выражен в виде рекурсии

Не силен в математике, но я вообще, честно говоря не понял даже значения «определенные на части множества возможных аргументов» Сначала создай подмножество из множества возможных аргументов, а затем вычисляй уже на этом подмножестве, и у тебя будет уже «определенные на всём множестве возможных аргументов»

Смысл в том, что по ф-и нельзя вычислить это «подмножество» допустимых аргументов.

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

с чего ты взял?

любую ли ф-ю вида 1 можно привести к виду 2. Ответ - нет.

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

с чего ты взял?

в смысле, где ты увидел тут выражение в виде рекурсии? Это же цикл у тебя, пусть и с сахаром.

Ну тогда ок, согласен.

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

Если у тебя на каждом шаге память нарастает - значит процесс рекурсивен

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

в смысле, где ты увидел тут выражение в виде рекурсии? Это же цикл у тебя, пусть и с сахаром.

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

Если бы хоть раз за это время показали, где указание на эту «цель» в посте топикстартера

Человек отличается от машины тем, что способен понимать контекст, а не просто воспринимать слова буквально. Ты, видимо, не способен, если вопроса ТС не понял. Если тебе хочется явных указаний - то обрати внимание на упоминание ТСом небезопасности рекурсии (то есть то самое использование стека).

Если у тебя на каждом шаге память нарастает - значит процесс рекурсивен

То есть, вот это:

fact=function(n){
  var result = 1, stack=[]
  while(n) stack.push(n--) 
  while(stack.length) result*=stack.pop() 
  return result
}

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

Существуют вычислимые по тьюрингу функции, которые не являются общерекурсивными

опять лжёшь :) или ты уже опроверг тезис чёрча-тьюринга?

это потому что ты ещё не понял рекурсию :)

область определения относится не к самой функции, а к оператору минимизации

опять лжёшь :)

Тезис Черча-Тьюринга устанавливает соответствие между частично-рекурсивными ф-ми и мт, а не между общерекурсивными и мт. Для общерекурсивных ф-й, ВНЕЗАПНО, проблема останова разрешима. А для мт - нет. Тебя это не смущает?

а к оператору минимизации

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

у тс-а в посте ничего кроме наркоманского бреда нет. какие цепи?

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

тезис чёрча-тьюринга постулирует эквивалентность множеств вычислимых и общерекурсивных функций.

Еще раз, для дебилов. МТ, соответствующие общерекурсивным функциям, _всегда завершаются_. Куда ты дел МТ, которые могут зависнуть?

эти функции НЕ являются вычислимыми по тьюрингу

эти функции НЕ являются вычислимыми по тьюрингу

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

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

Бред. «Итерационная форма» и примитивно-рекурсивные функции никак не связаны.

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

я не отрицаю, что общаться с необразованным быдлом непросто.

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

с альтернативной наукой прошу не беспокоить. это к фоменко и ко.

согласен, бред. но зачем ты его принёс сюда?

Напоминаю, что под «итерационной формой» понимается вычислительный процесс, во время исполнения которого не происходит динамического выделения памяти на каждой итерации.

Сам придумал?