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

А оптимизация как бы не всегда возможна … 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);
}

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

продукт сгенерированный gcc.

А при чём тут какой-то конкретный язык, да ещё сишечка, когда обсуждается работа железа?

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

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

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

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

А при чём тут какой-то конкретный язык, да ещё сишечка, когда обсуждается работа железа?

при чём тут железо, если мы обсуждаем

любая рекурсия может быть привращена в итеративную запись, правильно? (тезис Черча) подскажите алгоритм, который умеет символьно производить такую операцию, например для языков Java/C/C++ ? Может кто-то уже налабал готовый тул?

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

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

то, что в компиляторах рекурсия есть, и они порождают рекурсивный машинный код с использованием стека. А твои хаки с 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

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

при чём тут железо

Ну, как бы при том, что мой тезис состоит в следующем:

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

На первой странице этого треда. Для справки: компьютер — это железо.

то, что в компиляторах рекурсия есть

Никто не спорит.

и они порождают рекурсивный машинный код

А вот этого не существует.

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

Ты считаешь, компиляторы не порождают код, который читает адрес возврата из стека (запихнутый туда call-ом)?

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

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

Ну, как бы при том, что мой тезис состоит в следующем: Компьютер работает нерекурсивно.

с какого перепугу? Откуда ты вообще взял этот тезис?

Для справки: компьютер — это железо.

а ты == вода. Т.ч. сливайся.

А вот этого не существует.

есть вызов функции CALL, есть рекурсивная CALL. Детали реализации не отменяют факта наличия рекурсии.

Ты считаешь, компиляторы не порождают код, который читает адрес возврата из стека (запихнутый туда call-ом)?

компиляторам это не нужно. Компилятором нужно делать рекурсивный CALL, пример выше.

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

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

с какого перепугу?

Ну, с такого, что самого понятия рекурсия на этом уровне нет.

Т.ч. сливайся.

Деткам своим приказывать будешь.

Детали реализации не отменяют факта наличия рекурсии.

Детали реализации на этом уровне — это уже транзисторы. Мы говорим об интерфейсе.

компиляторам это не нужно.

Так считаешь, или нет?

есть вызов функции CALL, есть рекурсивная CALL.

rec:
goto rec;

У меня получился рекурсивный goto? =)

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

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

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

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

На первой странице этого треда.

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

Нет, память не выделяется.

for(i=0; i<10; i++)
    p[i]=malloc(100);

Это рекурсия?

Тред не читай, сразу отвечай.
В ООП для общего случая такого алгоритма не существует из-за полиморфизма (dynamic dispatch).
Погугли, например, почему Rich Hickey в Clojure сделал явный trampolining (loop-recur).

Вдогонку: если рассматривать не ООП, то, насколько я понимаю, чтобы преобразовывать автоматически нужно, чтобы программа была написана в CPS-стиле (как это сделано в Scheme).

Еще советую почитать (не совсем про это, но смежные темы):
CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. (by HG Baker)
и
http://www.more-magic.net/posts/internals-gc.html

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

Ну, с такого, что самого понятия рекурсия на этом уровне нет.

так считает учительница информатики в твоей школе? Что вообще значит «нет понятия»? Понятие «рекурсия» от «уровня» не зависит, как и от ЯП.

Детали реализации на этом уровне — это уже транзисторы. Мы говорим об интерфейсе.

это ты говоришь о каких-то «интерфейсах», а я говорю о вполне конкретном термине CS. Вот посмотри: http://en.wikipedia.org/wiki/Recursion Там в самом начале рекурсия в рекламе какао.

Ладно, вика для тебя наверное не авторитет. А профессор Дональд Кнут с рекурсией на уровне MIXAL'а тоже?

Так считаешь, или нет?

что за идиотский вопрос? Возможно компилятор из MSVC-2017 так и делает, я не в курсе. Давай пример кода, раз у тебя есть такие примеры. Если у тебя примеров нет, то хотя-бы скажи, зачем компиляторам такие хаки?

Т.ч. сливайся.

Деткам своим приказывать будешь.

дык я смотрю у тебя уровень знаний как у моего сына шести лет. Он тоже упоротый, и будет спорить до бесконечности. Если даже слился в споре, он «наколдует волшебный меч, и всех убьёт», как вчера высказался.

Т.ч. колдуй, детка. Как наколдуешь — возвращайся.

У меня получился рекурсивный goto?

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

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

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

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

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

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

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

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

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

ещё раз напоминаю, что для этого рекурсия не нужна, достаточно итерации.

e.g.

while(rand()%17!=7)
{
  char* s = malloc(rand()%1000);
}

ещё раз напоминаю, что для этого рекурсия не нужна, достаточно итерации.

Ну тогда рекурсия ни для чего не нужна, ведь для реализации любого control-flow достаточно while и присваивания. В частности, можно на них смоделировать стек.

да. Это вырожденный тривиальный и минимальный случай рекурсии.

но значит while - это тоже тривиальный и минимальный случай рекурсии? Чем while отличается от этого гото?

Ноль тоже можно считать натуральным числом(и некоторые математики так считают).

Наоборот - некоторые ретрограды на постсоветском пространстве (и только они) ноль натуральным не считают. Но таких со временем все меньше.

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

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

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

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

Давай пример кода, раз у тебя есть такие примеры.

Посмотри, как реализован setjmp, например.

Что вообще значит «нет понятия»? Понятие «рекурсия» от «уровня» не зависит, как и от ЯП.

Оно бессмысленно. Ты можешь сказать «рекурсивная кастрюля», но это не значит ничего.

это ты говоришь о каких-то «интерфейсах», а я говорю о вполне конкретном термине CS.

Я говорю об интерфейсе команды CALL. Так вот: все эти «детали» — это элементы именно интерфейса. Потому что они прекрасно видны остальному коду.

А профессор Дональд Кнут с рекурсией на уровне MIXAL'а тоже?

А дай цитатку.

Ну тогда рекурсия ни для чего не нужна, ведь для реализации любого control-flow достаточно while и присваивания. В частности, можно на них смоделировать стек.

можно конечно. Но это будет скорее эмуляция, нежели чем полноценный вызов подпрограммы, как в x86 CALL.

но значит while - это тоже тривиальный и минимальный случай рекурсии? Чем while отличается от этого гото?

условием очевидно.

Наоборот - некоторые ретрограды на постсоветском пространстве (и только они) ноль натуральным не считают. Но таких со временем все меньше.

ну вот, началось… Ещё и нацпол приплёл. Лично я считаю как Екклесиаст: «чего нет, то нельзя считать». Ну давай, назови меня сионистом и ещё как-нить.

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

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

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

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

Посмотри, как реализован setjmp, например.

вот ты и покажи, не хочу в говне мамонта ковыряться.

Оно бессмысленно. Ты можешь сказать «рекурсивная кастрюля», но это не значит ничего.

для меня слово «尻» тоже ничего не значит. Просто я не знаю японский язык.

Я говорю об интерфейсе команды CALL. Так вот: все эти «детали» — это элементы именно интерфейса. Потому что они прекрасно видны остальному коду.

«интерфейсы» тут не при чём. Речь про рекурсию. А сам «интерфейс» может быть совсем другим, какая нафиг разница? В PDP-11 такой команды не было, просто потому, что там можно было и без этой команды сделать IP→[--SP], ADDR→IP. Какая разница?

А дай цитатку.

а купи книжки и прочитай. Если нищеброд, есть на торрентсру.

вот ты и покажи, не хочу в говне мамонта ковыряться.

Забанили в гугле? Бывает, ничего страшного.

для меня слово «尻» тоже ничего не значит. Просто я не знаю японский язык.

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

А комп от кастрюли отличается не настолько принципиально.

А сам «интерфейс» может быть совсем другим, какая нафиг разница?

Если мы работаем хотя бы на уровне C — никакой. Если на уровне ассемблера или машкодов — большая.

В PDP-11 такой команды не было

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

а купи книжки и прочитай

Куплено, прочитано. Надеюсь, ты не ждёшь, что я буду учить её наизусть?

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

Куплено, прочитано. Надеюсь, ты не ждёшь, что я буду учить её наизусть?

я надеюсь, ты осилишь найти то место, в котором «появляется рекурсия». Не заставляй меня тащится к книжной полке и искать самому. Мне лень.

я надеюсь, ты осилишь найти то место, в котором «появляется рекурсия».

Нет, не осилю. Ибо его там нет.

Но это будет скорее эмуляция, нежели чем полноценный вызов подпрограммы

А какая разница?

условием очевидно.

Не понял. То есть если в гото добавить условие, то это не будет рекурсией?

ну вот, началось… Ещё и нацпол приплёл. Лично я считаю как Екклесиаст: «чего нет, то нельзя считать». Ну давай, назови меня сионистом и ещё как-нить.

При чем тут что можно считать и что нельзя?

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

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

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

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

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