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

в итерации ты просто последовательно перебираешь множество.

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

(define tst (lambda(lst) (if (not (null? lst)) (do-staff))))

Воздержался и прохожу мимо.

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

Ты не понял. Твоя поповская собака рекурсивна лишь до тех пор, пока мы рассматриваем её как рекурсивную, т.е. условно говоря «пусть х - история, тогда х = начало+х+конец». А если рассматривать её как последовательность одинаковых фраз, т.е. х = начало*n+конец*n, где n=∞, то это итеративная задача.

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

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

Нет, не превратиться. Подумай о степени роста твоего «состояния».

Благодарю Вас.

Нет, не превратиться. Подумай о степени роста твоего «состояния».

Вы имеете в виду рост на реальной машине? Если не на машине а вообще - то процесс линейный и бесконечный, это даже не рост собственно, ну и что?

Нет, не превратиться. Подумай о степени роста твоего «состояния».

И что? Теперь любой прожорливый к памяти алгоритм будем называть от этого рекурсивным?

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

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

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

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

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

Рекурсивного алгоритма.

Совершенно верно.

Тебе где-то придётся запоминать, куда тебе вернуться

И что, нельзя это запоминание реализовать в цикле?

нет. Только с дополнительным стеком. Или попробуй сделать обход бинарного дерева или qsort циклом, что-бы опровергнуть мои слова.

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

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

Тем и отличается рекурсия от итерации, в итерации ты просто последовательно

А кто запрещает прыгнуть назад при переборе?

то, что в одном числе(счётчике итераций) хранится одно число. Потому прыгать ты можешь только вперёд, и только на одну итерацию. Иначе это уже не итерации.

Да какая разница со стеком или без стека, или с 10 стеками? Вопрос не в этом.

Тебе где-то придётся запоминать,

стек уже отменили?

да. Стек из одного числа уже отменили.

Да? А в двух счетчиках сколько хранится чисел? А в 100?

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

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

Кто сказал, что из одного? О чем ты?

Машина Тьюринга тоже о рекурсии не знает.

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

нет. Только с дополнительным стеком. Или попробуй сделать обход бинарного дерева или qsort циклом, что-бы опровергнуть мои слова.

То есть если программа требует дополнительную память, она уже рекурсивная?

Не «именно для рекурсии», а «именно для вызова подпрограмм».

пруф можно? Из подпрограмм можно возвращаться без всякого стека. Я возвращался, делал тест памяти для Z80. Оно у меня вообще без памяти работало.

У тебя какое-то очень извращенное понятие об итерации.

Какая вообще разница, свой стек или системный?

stack-overflow же.

Какая вообще разница, свой стек или системный?

BTW, всегда хотел узнать, а почему в массы пошла машина Тьюринга а не Поста? Ведь машина Поста проще, а значит более подходящая в качестве формализма?

Тогда ответь на следующие вопросы:

у тебя собеседование на носу что-ли? А я значит бесплатный репетитор для тебя?

К тому, что я любой алгоритм могу вывернуть и в рекурсию, и в итеративный процесс.

«итеративный» он будет лишь при наличии дополнительной памяти неизвестного объёма. Потому в кавычках. Без кавычек итеративен лишь алгоритм требующий O(1) памяти.

Естественно стек можно юзать какой угодно, не обязательно тот, что в CPU на esp.

у тебя собеседование на носу что-ли? А я значит бесплатный репетитор для тебя?

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

«итеративный» он будет лишь при наличии дополнительной памяти неизвестного объёма. Потому в кавычках. Без кавычек итеративен лишь алгоритм требующий O(1) памяти.

Вот тут уже хотя бы что-то стало проясняться.

Правильно ли я понимаю, что любой алгоритми, требующий больше O(1) памяти, уже будет рекурсивным?

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

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

важен контекст. Если он один, или он всегда одинаковый — это итерация. Если контекстов много — рекурсия. Например (n-1)!*n это рекурсивное определение факториала, потому-что внутреннее определение нельзя вынуть из контекста, оно не на хвосте. Нужно существенно переделать алгоритм, например умножать в другом порядке, не от n, а от 1, тогда будет итерация. Но это уже другой алгоритм(реализация). В данном случае — не имеет значения(если нет потерь точности).

в итерации ты просто последовательно перебираешь множество.

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

конечно. Ибо итерация — частный случай рекурсии.

о чем вы тут вообще оба? Итерация - это тоже рекурсия.

Да какая разница со стеком или без стека, или с 10 стеками? Вопрос не в этом.

вопрос и разница именно в этом. При итерации у тебя либо один контекст, либо n+1-й контекст прямо следует из n-ного.

Ты путаешь понятие рекурсивного алгоритма с понятием рекурсивного процесса. Тебе тут уже объяснили.

А в двух счетчиках сколько хранится чисел? А в 100?

в C счётчиках хранится O(C) === O(1) чисел.

Кто сказал, что из одного? О чем ты?

о том, что константа эквивалентна единице. Она не растёт. Т.е. если алгоритм требует Over9000 байтов, но это константа, то этот алгоритм, будучи итеративным, может выполнять ЛЮБОЕ число итераций. А если рекурсивный, то память рано или поздно кончится. ЛЮБАЯ память. В этом и разница.

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

То есть если программа требует дополнительную память, она уже рекурсивная?

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

У тебя какое-то очень извращенное понятие об итерации.

у Кнута и в SICP тоже самое. Но вы же не читали...

всегда хотел узнать, а почему в массы пошла машина Тьюринга а не Поста?

ты ещё спроси, что слаще, хрен или редька? И почему массы говорят «хрен его знает», а не «редька в курсе»?

Какая разница-то? AFAIK Тьюринг более внятно всё написал.

Правильно ли я понимаю, что любой алгоритми, требующий больше O(1) памяти, уже будет рекурсивным?

нет, неправильно. Конечно любой алгоритм можно переписать так, что-бы на n шагов он пожрал O(n!) памяти. Дурное дело не хитрое.

Какая разница-то?

Разница в том, что:

машина Поста проще, а значит более подходящая в качестве формализма.

а ты — один из тех быдлокодеров, которые считают, что куча бесконечная? 640К кучи всем хватит?

машина Поста проще, а значит более подходящая в качестве формализма.

из «проще» совсем не следует «подходит».

Ну и само понятие «проще» ты не формализовал. Или ты про мнение авторов википедии?

Ну и само понятие «проще» ты не формализовал. Или ты про мнение авторов википедии?

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

Turing's paper was received for publication in May 1936, followed by Post's in October

и, при этом:

were developed independently

Мы верим, да, да

Ну и само понятие «проще» ты не формализовал

Ну а проще - значит содержит меньше сущностей. Не?