взаимно :)

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

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

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

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

сомневаюсь.

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

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

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

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

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

сомневаюсь.

Зря.

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

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

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

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

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

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

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

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

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

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

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

Кроме того:

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

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

на всем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ты лжёшь.

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

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

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

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

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

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

функция которая использует стек (в любом виде) - рекурсивная. Не важно, в каком виде ты рекурсию _записываешь_ - либо в виде 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дружок, ну зачем ты повторяешь раз за разом выдуманную ересь? Возьми и открой учебник, там же все написано.

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

Да. Это то, что следует понимать под итерационной формой, чтобы содержательно ответить на вопрос ОПа. Если ты обсуждать вопрос ОПа не хочешь, а зашел сюда просто повыебываться - то проходи мимо.

Ну или можешь предложить свои варианты определения рекурсивного/итерационного процесса.

таблетки принять забыл?

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

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

тезис — он на то и тезис, что его ни доказать, ни опровергнуть не выходит.

А где я говорил, что его можно доказать? Еще раз - эквивалентность частично-рекурсивных ф-й, лямбд и МТ - это не тезис Черча-Тьюринга. Это просто теорема. Она доказана, да, четко и строго. Эта теорема стала причиной того, что тезис был сформулирован. Сам тезис заключается в том, что неформальное понятие «вычислимой функции» было предложено определять как «ф-я, представимая в одной из вышеперечисленных эквивалентных форм».

русская терминология в области мат логики весьма убога, да.

При чем тут русская терминология, дебилушка?

Вот тебе цитаты, с-но, авторов тезиса: [qoute] THESIS I. Every effectively calculable function (effectively decidable predicate) is general[28] recursive [Kleene's italics] «Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it ... так и написано - „возьмем в качестве определения эффективное вычислимой функции понятие частично-рекурсивной ф-и“ (что эквивалентно лямбдам и МТ, как было доказано перед этим, что и послуэило причиной формулирования тезиса).

А где я говорил, что его можно доказать?

Это просто теорема.

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

При чем тут русская терминология, дебилушка?

Every effectively calculable function (effectively decidable predicate) is general[28] recursive

слово «general» твой межушный ганглий способен перевести?

update

так и написано - „возьмем в качестве определения эффективное вычислимой функции понятие частично-рекурсивной ф-и“

понял. неспособен. соболезную.

тогда с тебя точная формулировка тезиса

Я для кого выше цитату дал?

«This heuristic fact [general recursive functions are effectively calculable] ... led Church to state the following thesis(22). The same thesis is implicit in Turing's description of computing machines(23). „THESIS I. Every effectively calculable function (effectively decidable predicate) is general[28] recursive [Kleene's italics] „Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it ...“[29] “(22) references Church 1936 »(23) references Turing 1936–7

слово «general» твой межушный ганглий способен перевести?

Слово general относится не к тотальности ф-й, а к типу рекурсии (general recursion, рекурсия общего вида, в отличии от примитивной рекурсии), то есть general recursive functions - это частично-рекурсивные функции. А общерекурсивные (тотальные, то бишь) ф-и так и называются total recursive functions. А ты - долбоеб.

Кстати, теб даже на русской википедии специально про это указали:

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

Но ты же дебил, дочитать до конца не способен.

general recursive functions - это частично-рекурсивные функции

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

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

Ебанько, открой уже учебник и прочитай, какие функции называются general recursive, а какие - total recursive.

Вот тебе чтобы не искал: http://people.ucalgary.ca/~rzach/static/open-logic/computability/recursive-fu...

и вот: http://math.stackexchange.com/questions/75296/what-is-the-difference-between-...

и еще: http://www.cs.cmu.edu/~cdm/pdf/PrimRec-6up.pdf

аналога «general recursive» (это термин из метаматематики гёделя) афаик в русском вообще нет. сейчас используются общерекурсивные (total recursive) и частично-рекурсивные (partial recursive).

http://math.stackexchange.com/questions

тоже прохладно.

открой клини, наконец. его на русский ещё при ссср переводили.

аналога «general recursive» (это термин из метаматематики гёделя) афаик в русском вообще нет.

Ебанько, general recursive = partial recursive. 57-58 слайд в третьей пдфке, ебанько. Или почитай того же Клини, у него это все тоже написано.

занятно. т.е. ты не читаешь перед тем как постить?

Вот тебе чтобы не искал: http://people.ucalgary.ca/~rzach/static/open-logic/computability/recursive-fu...

Clearly every general recursive function is total.

рекурсивная => нерекурсивная реализация (комментарий)

:)

алсо

So the word \general," a historic relic, is a misnomer; on the surface

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

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

А вообще: http://mathworld.wolfram.com/GeneralRecursiveFunction.html

Так что надо смотреть на конкретные определения. У Черча и Тьюринга general = partial.

авторитет stackexchange для меня не превышает местный; третья ссылка напугала слайдами — я плохо воспринимаю информацию, отформатированную для умственно-отсталых.

теперь рассказывай в каком опиумном притоне «general» переводят как «частичный».

я тебе выше объяснял, что между «general recursive function» гёделя (кстати, именно с твоего кукареканья поэтому поводу и началась наша беседа) и «total recursive function» чёрча прошло слишком мало времени (интернетов тогда не было, да) и они приехали в ссср одновременно и получили один перевод на двоих.

У Черча и Тьюринга general = partial.

обоснуй

теперь рассказывай в каком опиумном притоне «general» переводят как «частичный».

Его не переводят как частный, при чем тут вообще перевод? Речь о том, что general и partial используются как синонимы. А когда речь идет о тотальности, то так и говорят - total.

кстати, именно с твоего кукареканья поэтому поводу и началась наша беседа

Напомню, что это ты начал кукарекать про мифическую, одному тебе известную «теорию Геделя».

и они приехали в ссср одновременно и получили один перевод на двоих.

Да при чем тут, когда они приехали в СССР? При чем тут вообще перевод?

Речь о том, что general и partial используются как синонимы.

это какой-то неологизм. ни чёрч, ни тьюринг о нём, к сожалению, ничего не знали. насколько я понял по вольфраму (на соседней странице про «рекурсивные функции» без предваряющих прилагательных взаимоисключающие параграфы детектед... так что отношение к ресурсу соответствующее), существует секта, которая утверждает что general = total + partial, и ты являешься её адептом (хотя из твоих слов вытекает более дикое и нелогичное утверждение).

Напомню, что это ты начал кукарекать про мифическую, одному тебе известную «теорию Геделя».

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

Да при чем тут, когда они приехали в СССР? При чем тут вообще перевод?

при том что мы общаемся на русском?

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

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

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

Или, иначе - у нас может быть некоторое подмножество МТ и их начальных данных таких, что не существует тотальной ф-и на этом подмножестве, которая на нем решает задачу разрешимости, но при этом может вполне существовать нетотальная ф-я на всем множестве МТ+данные, которая в точности на всех МТ+данные подмножества проблему останова решает, а на остальных МТ+данные - виснет.

И, значит, расширив множества МТ+данных неким надмножеством, мы можем задать нетотальную ф-ю на этом надмножестве, которая будет в точности решать полностью задачу останова для всех МТ+данные (точнее не то, что можем, но «неразрешимость» не запрещает нам так делать, вот в чем суть). Отлично, чо. Какой смысл в такой неразрешимости тогда?

существует секта, которая утверждает что general = total + partial

Все с точностью до наоборот. Это у вас секта.

при том что мы общаемся на русском?

если говорить о русском, то тут все понятно - вычислимые = частично-рекурсивные, частично-рекурсивные = вычислимые > общерекурсивные.

Вопрос исключительно об английском - что значит general.

которые на нашем подмножестве определены лишь _частично_

На множестве - частично, а на подмножестве - полностью, конечно, selffix.

разработал теорию рекурсивных функций.

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

вот и я говорю: путаница с терминологией просто грандиозна.

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

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

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

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

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

В таком определении «вычислимости» получается, например, что невычислимость проблемы останова не говорит о том, что нету алгоритма, который бы мог решить проблему останова. Это же чепуха. Зачем такая «вычислимость» вообще нужна тогда?

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

дык перепиши обход бинарного дерева, что тебе мешает?

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

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

Т.е. компиляторы существуют, вот только они не работают как в твоих влажных фантазиях.

функция которая использует стек (в любом виде) - рекурсивная.

нет.

int f(int x)
{
  return x*x;
}

int main()
{
  return f(7);
}

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

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

А вот в функции Аккермана такой вариант уже не сработает.

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

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

#include <stdio.h>

int fact(int N) {
        if (N < 1) return 1;
        else return N * fact(N - 1);
}

int main () {
        return fact(10);
}

_Z4facti:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6                                                                                                                                                           
        subq    $16, %rsp                                                                                                                                                                 
        movl    %edi, -4(%rbp)                                                                                                                                                            
        cmpl    $0, -4(%rbp)                                                                                                                                                              
        jg      .L2                                                                                                                                                                       
        movl    $1, %eax                                                                                                                                                                  
        jmp     .L3                                                                                                                                                                       
.L2:                                                                                                                                                                                      
        movl    -4(%rbp), %eax                                                                                                                                                            
        subl    $1, %eax                                                                                                                                                                  
        movl    %eax, %edi                                                                                                                                                                
        call    _Z4facti                                                                                                                                                                  
        imull   -4(%rbp), %eax                                                                                                                                                            
.L3:                                                                                                                                                                                      
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   _Z4facti, .-_Z4facti
        .globl  main
        .type   main, @function
main:
.LFB1:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movl    $10, %edi
        call    _Z4facti
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

оптимизацию включи.

А оптимизация как бы не всегда возможна:

#include <stdio.h>

int fact(volatile int N) {
        if (N < 1) return 1;
        else return N * fact(N - 1);
}

int main () {
        return fact(1000);
}

$gcc -S -O2 main.c

.LHOTB0:
        .p2align 4,,15
        .globl  _Z4facti
        .type   _Z4facti, @function
_Z4facti:
.LFB30:
        .cfi_startproc
        subq    $24, %rsp
        .cfi_def_cfa_offset 32
        movl    $1, %eax
        movl    %edi, 12(%rsp)
        movl    12(%rsp), %edx
        testl   %edx, %edx
        jle     .L2
        movl    12(%rsp), %edi
        subl    $1, %edi
        call    _Z4facti
        movl    12(%rsp), %edx
        imull   %edx, %eax
.L2:
        addq    $24, %rsp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE30:
        .size   _Z4facti, .-_Z4facti
        .section        .text.unlikely
.LCOLDE0:
        .text
.LHOTE0:
        .section        .text.unlikely
.LCOLDB1:
        .section        .text.startup,"ax",@progbits
.LHOTB1:
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB31:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $999, %edi
        call    _Z4facti
        addq    $8, %rsp
        .cfi_def_cfa_offset 8
        imull   $1000, %eax, %eax
        ret
        .cfi_endproc
.LFE31:
        .size   main, .-main
        .section        .text.unlikely
.LCOLDE1:
        .section        .text.startup

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

А оптимизация как бы не всегда возможна … volatile

ты идиот?

00000000004004a0 <main>:
  4004a0:	85 ff                	test   edi,edi
  4004a2:	b8 01 00 00 00       	mov    eax,0x1
  4004a7:	7e 0f                	jle    4004b8 <main+0x18>
  4004a9:	0f 1f 80 00 00 00 00 	nop    DWORD PTR [rax+0x0]
  4004b0:	0f af c7             	imul   eax,edi
  4004b3:	83 ef 01             	sub    edi,0x1
  4004b6:	75 f8                	jne    4004b0 <main+0x10>
  4004b8:	f3 c3                	repz ret 

$ gcc --version
gcc (GCC) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.

int fact(int N) {
        if (N < 1) return 1;
        else return N * fact(N - 1);
}

int main (int argc, const char* argv[]) {
        return fact(argc);
}

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

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

И что, собственно?

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

объясни безмозглому: зачем нужен «рекурсивный опрос регистра устройства»?

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

И что, собственно?

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

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

Только в каждом вызове своя n. Так что ничо он не делает.

Только в каждом вызове своя n. Так что ничо он не делает.

для 5! перед умножением в стеке будет

5,r_ptr,4,r_ptr,3,r_ptr,2,r_ptr

Умножаться будет в обратном порядке

2*3*4*5

1. хранит числа(5,4,3,2) в регистре

2. умножает числа во время их генерации. При этом порядок меняется на

5*4*3*2

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

объясни безмозглому: зачем нужен «рекурсивный опрос регистра устройства»?

предлагаю безмозглому прочесть что такое active polling/busy waiting.

предлагаю безмозглому прочесть что такое active polling/busy waiting.

читал. Не нашёл слова «рекурсия». Может мордой меня ткнёшь?

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

То есть компилятор просто поменял рекурсивный алгоритм на нерекурсивный (то есть на совершенно другой). Как это отменяет тот факт, что:

1. рекурсивный алгоритм принципиально невозможно записать итерационно

2. преобразование рекурсивного алгоритма в нерекурсивный в общем случае невозможно (да и вообще очень редко возможно)

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

именно так. Хоть это и другой алгоритм, но он эквивалентен исходному.

1. рекурсивный алгоритм принципиально невозможно записать итерационно

я этого и не говорил, как раз наоборот: многие рекурсии невозможно сделать итерацией. Я говорил, что итерационно можно не только TCO делать, но и НЕ хвостовую рекурсию тоже иногда можно развернуть. Конечно не всегда.

2. преобразование рекурсивного алгоритма в нерекурсивный в общем случае невозможно (да и вообще очень редко возможно)

IRL вполне себе возможно во многих _частных_ случаях. В общем конечно нет.

Вообще говоря, всё зависит от контекста: если контекст константный(в т.ч. отсутствует), то рекурсию всегда можно развернуть. Также рекурсию можно развернуть, если контекст может быть выражен итерационной формулой(не смог сходу нагуглить определение, только пример: https://ru.wikipedia.org/wiki/Итерационная_формула_Герона ), если рекурсия не хвостовая, итерационная формула должна допускать обращение (т.е. из x(n) можно вычислить не только x(n+1), но и x(n-1)).

я этого и не говорил, как раз наоборот: многие рекурсии невозможно сделать итерацией. Я говорил, что итерационно можно не только TCO делать, но и НЕ хвостовую рекурсию тоже иногда можно развернуть. Конечно не всегда.

Хвостовая рекурсия сама по себе итерационна. Она порождает итерационный control-flow. По-этому ее разворачивание в цикл тривиально, при этом алгоритм _не меняется_. В примере с алгоритмом же мы как раз поменяли рекурсивный алгоритм на нерекурсивный. Но рекурсивный алгоритм без рекурсии (то есть без недетерменированного выделения памяти) записать невозможно.

Вообще говоря, всё зависит от контекста: если контекст константный(в т.ч. отсутствует)

Это тогда и не рекурсия, очевидно.

Хвостовая рекурсия сама по себе итерационна. Она порождает итерационный control-flow. По-этому ее разворачивание в цикл тривиально, при этом алгоритм _не меняется_.

вот «меняется VS не меняется» — вопрос спорный на самом деле.

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

т.е. по твоему алгоритм x! := x*(x-1)! рекурсивным не является?

вот «меняется VS не меняется» — вопрос спорный на самом деле.

Ничего спорного.

т.е. по твоему алгоритм x! := x*(x-1)! рекурсивным не является?

Можно заранее выделить нужное количество памяти, то есть да - не является. Его можно перезаписать итерационно так (причем сам алгоритм и control-flow не меняя!) что ты там рекурсии в принципе не разглядишь.

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