рекурсия и итерация

Сравните схемки:

рекурсивный процесс

итеративный процесс

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

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

sicp я прочитал, дальше что?

Тут я вполне рекурсию вижу.

Вот тут не вижу:

while(..){
    void* x = malloc(100);
    ...
}

А emulek говорит, что она есть.

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

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

естественно. Формула типа 2+2*2 является рекурсивной. Калькулятор тоже. Такое нельзя обработать итерацией, ибо нужно возвращаться, в данном случае нужно вернутся к сложению после умножения, что-бы получить правильный ответ 6.

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

ну тем более — ажно два машинных стека. К тому же, в ZX-Spectrum именно так калькулятор и был реализован (который в EEPROM с Basic) — два стека, один вверх рос, второй навстречу. В обычном, том, что по SP, хранились операторы вроде +,-,*,/, а во втором хранились числа. Обрабатывалось это всё рекурсивной функцией, какой-то INTxx, да, прерывание.

А ещё любая программа на FORTH'е...

да. И почти любая на сишечке (за исключением твоих хэлловорлдов конечно).

ты все еще веришь, что стек «быстрее» произвольного массива?

как он может быть не быстрее, если он железный, а массив == твой велосипед? Разве в твоём процессоре есть инструкция для записи в память по индексу с постдекриментом кроме push? А твои велосипеды в любом случае будут не быстрее.

И это несложно проверить при желании. Вот ты-бы чушь не порол, а взял-бы, и проверил. На своём процессоре.

внутри http://pre.racket-lang.org/racket/collects/mred/private/wx/common/rbtree.rkt

ну вот и сравни с любой сишной реализацией. Разница в скорости, как у ракеты «Союз» со светом. Да, ракета — быстрая. По сравнению с телегой.

С учётом того, что списки там чаще, чем вектора, там сортировка слиянием.

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

Или хочешь сказать, что (define (fact n) (if (> n 1) (* (fact (- n 1)) n) 1)) Читается проще

Конечно проще, ибо смысл операций >,*,- мне знаком со школьной скамьи, а вот что значит операции apply и range я могу только догадываться.

Если для тебя не так, то поздравляю: у тебя lisp головного мозга.

да.

Нет. В форте совсем другая модель вычислений.

как он может быть не быстрее, если он железный, а массив == твой велосипед?

Стек - это обычная область памяти, такая же, как и массив. По-этому стек ничуть не быстрее массива

В смысле «другая»? Там стек же. Там действительно почти все процессы будут рекурсивными, разве нет?

ну вот и сравни с любой сишной реализацией. Разница в скорости, как у ракеты «Союз» со светом. Да, ракета — быстрая. По сравнению с телегой.

Не факт, на самом деле. Из-за сборщика мусора сишка как раз может оказаться тут телегой.

В сишке нет не то, что сборщика. В нем и памяти-то динамической нет - все библиотеками реализуется. Потому как сделаешь, так и будет.

В сишке нет не то, что сборщика.

Ну да, нету. В этом и проблема - сборщик мусора это ракета, а сишковский маллок - телега.

как он может быть не быстрее, если он железный, а массив == твой велосипед?

Ну не быдло ли ты? Повторяю вопрос для недоумков: доступ к адресу по смещению от ESP чем-то отличается от доступа по, допустим, EAX?

Разве в твоём процессоре есть инструкция для записи в память по индексу с постдекриментом кроме push?

В моем процессоре, как и в любом, сделанном в последние 15 лет, push раскрывается в точно такую же последовательность uops, как и явный постдекремент регистра.

Вот ты-бы чушь не порол, а взял-бы, и проверил.

Ты, баття, редкостное ничтожество. Я удивляюсь, как ты до сих пор от стыда не повесился? Или тебе реально не стыдно быть настолько самоуверенной некомпетентной шлюхой?

сишковский маллок - телега.

Это всего-лишь библиотека. Сборщик может быть сделан в другой библиотеки(Boehm GC, например). Для сишечки это не важно - как скажешь, так и будет. В то время как опыт пользования программ с GC говорит об их тормозах по сравнению с сишечными или плюсовыми.

Вот она, квинтэссенция маразма - рекурсивный значит выделяющий память. Браво!

если ты включишь голову, то поймёшь, что так и должно быть — рекурсивная функция, в отличие от итеративной, работает в персональном окружении(контексте), в этом и есть отличие. А как ты прыгаешь по коду — вопрос десятый, хоть call/ret, хоть loop. Да и ЯП тут не при чём.

Это хорошо, ибо в таком виде он более понятен для разных жаба/php-обезьян. Сишник такую рекурсию разворачивает ещё в подкорке. Но тебе видимо не осмыслить программирование без std::append(), потому конструкция вроде *s++ для тебя «опасная» и «непонятная».

Твой уровень аргументации просто фееричен. Не важно, хороший это код или плохой, важен твой ответ на вопрос, рекурсивен ли он.

тебе нечего возразить? Сливайся молча. Твоя фееричная демагогия никому не интересна. Как и твоё личное отношение лично ко мне.

sicp я прочитал, дальше что?

самое сложное: понять прочитанное.

А emulek говорит, что она есть.

здесь нет рекурсии. И здесь её нет:

void foo()
{
  foo();
}

Нет. В форте совсем другая модель вычислений.

The mistery of Yoda’s speech uncovered is: Just an old Forth programmer Yoda was

тоже самое, на самом деле. Такая модель очень часто используется внутри компиляторов и интерпретаторов. В железе её тоже часто реализуют. Просто очень непривычно выглядит первое время. Но привыкнуть несложно.

Стек - это обычная область памяти, такая же, как и массив. По-этому стек ничуть не быстрее массива

стек — обычная область памяти, согласен. Но для работы со стеком есть специальные команды и регистры. (sp,bp), позволяющие намного ускорить типичные операции стека(коих всего две — затолкать/вытолкать). Кроме того, есть специальная форма заталкивания/выталкивания регистра ip, которая не имеет аналога для простого массива. Потому сохранять можно не только данные, но и адреса кодов. Именно это и нужно при рекурсии, не просто вернуться, а запомнить _путь_, куда надо возвращаться. Велосипедить это всё указателями на функции или виртуальными функциями — жуткий геморрой и тормоза.

Не факт, на самом деле. Из-за сборщика мусора сишка как раз может оказаться тут телегой.

это если у тебя рукожопие.

Ну да, нету. В этом и проблема - сборщик мусора это ракета, а сишковский маллок - телега.

пиши свой СБИШ или возьми из ракеты. В чём проблема?

В моем процессоре, как и в любом, сделанном в последние 15 лет, push раскрывается в точно такую же последовательность uops, как и явный постдекремент регистра.

пруф будет?

тебе нечего возразить? Сливайся молча. Твоя фееричная демагогия никому не интересна. Как и твоё личное отношение лично ко мне.

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

Ошибаешься, здесь рекурсия есть.

Конечно проще, ибо смысл операций >,*,- мне знаком со школьной скамьи, а вот что значит операции apply и range я могу только догадываться.

А брейнфак тогда еще проще, ок.

Ты же отвечаешь не по существу

ответ по существу ты очевидно не осилил. А он выше уже был.

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

твои алгоритмы не имеют смысла. В математике это как сокращение дроби на ноль — доказать можно всё что угодно. Но зачем?

Ошибаешься, здесь рекурсия есть.

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

твои алгоритмы не имеют смысла. В математике это как сокращение дроби на ноль — доказать можно всё что угодно. Но зачем?

Алгоритмы? Мои? Был только сишный код, не мой, который ты так и не можешь толком отнести ни к рекурсивному, ни к интеративному.

foo выражается через саму себя. Вот и рекурсия.

пруф будет?

Замени везде в коде хрень вроде pushl %edi на movl 0(%esp), %edi; addl $1, %esp, и убедись, что разницы в производительности нет.

И это я еще молчу о том, что никто тебе не запрещает использовать esp для своего массива, и игнорировать системный ABI с его стеком вообще.

то есть, movl %edi, 0(%esp)

Конечно проще, ибо смысл операций >,*,- мне знаком со школьной скамьи, а вот что значит операции apply и range я могу только догадываться.

А брейнфак тогда еще проще, ок.

в некотором смысле — проще. Хотя писать на нём и сложнее. Он слишком простой, и тривиальная конструкция там занимает слишком много букв. Можно придумать простой естественный язык, ароде русского мата, но ты устанешь объяснять на этом языке что угодно сложнее «fuck off».

Алгоритмы? Мои? Был только сишный код, не мой, который ты так и не можешь толком отнести ни к рекурсивному, ни к интеративному.

дык мы про код говорим? Тогда я не знаю, что такое «рекурсивный код». Я знаю, что такое «рекурсивный алгоритм».

с т.з. алгоритма нет никакой разницы, что через что выражается. С т.з. алгоритма там безусловный jmp, и запись одного и того же числа в ячейки [sp], [sp-1], [sp-2],... Т.к. число только записывается, и ничего более, то совершенно не важно, что это за число.

Замени везде в коде хрень вроде pushl %edi на movl 0(%esp), %edi; addl $1, %esp, и убедись, что разницы в производительности нет.

на что мне менять call/ret?

то есть, movl %edi, 0(%esp)

это по любому длиннее(особенно с учётом inc/dec), а значит не влезет в кеш. Уже получишь тормоза, чисто из-за раздутого кода.

Ну как нет, если рекурсия по определению - код который вызывает себя.

Можно придумать простой естественный язык, ароде русского мата, но ты устанешь объяснять на этом языке что угодно сложнее «fuck off».

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

А если с выводом типа?

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

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

на что мне менять call/ret?

Посмотри, как это сделано в ARM, где никаких call и ret нет в принципе.

нет.

там фишка в ныне ставшим модном «рефакторинге»

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

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

в компиляторах/интерпретаторах редко когда прямо манипулируют со стеком возвратов

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

ТОЛЬКО русским матом ты не сможешь почти ничего КОНКРЕТНОГО объяснить. Кроме эмоций. Да, иногда этого достаточно. Но в этом случае можно и промолчать. Чё пи**ть попусту?

Алгоритмы — сплошная конкретика, и ты слишком много сил потратишь для изготовления конкретного float'а на BF'е. Попробуй, если не веришь. Нет, я знаю, что это возможно, и это не сложно. Но очень долго.

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

всё зависит от задачи. Иногда без этого никак, иногда это только мешает.

Ну как нет, если рекурсия по определению - код который вызывает себя.

ок. Это будем считать рекурсией кода. А моё определение (которое я выдрал из SICP) — определение рекурсивного алгоритма.

Так без вопросов?

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

Это все соплями по говну рассусоливание.

Ты как, успокоился?

Если да, то похмелись, и попытайся понять: Изначально я говорил про автоматические переменные в сишечке. Компилятор вовсе не обязательно их пихает в стек. В современных CPU amd64 и регистров полно, а регистры понятно быстрее(глупо с этим спорить, да). Туда и пихает.

Т.е. автоматические переменные в сишечке пихаются в регистры и/или в стек, в зависимости от того, что быстрее(в целевом CPU). Есть два следствия:

1. т.к. основные переменные критичные по времени лежат в регистре/стеке, то вся программа работает обычно в разы быстрее. Доступ к регистром в разы быстрее. Доступ к стеку несколько быстрее потому, что он всегда в кеше, но важно то, что освобождение/выделение памяти стека практически мгновенно, по сравнению с любым GC.

2. п1 это хорошо, но что плохо, эти переменные не разруливаются GC. Невозможно вернуть в пул то, чего там никогда не было. А регистров/стека там никогда не было. Потому в сишке нельзя сделать «полноценный» GC. Это плата за наличие быстрых переменных, которые в регистрах и/или в самой быстрой памяти (в стеке, для некоторых CPU).

Ты не обязан платить такую цену, если хочешь, делай ВСЕ свои переменные своим аллокатором. И они будут убираться твоим любимым GC. Как в любимой яве/пхп/сишарп.