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

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

Ну как же, бритва оккама

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

О рекурсивных процессах, кажется, никто не говорил, нет?

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

Что и требовалось доказать =)

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

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

есть мыслепостигаемое отличие:

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

рекурсия же действие которое для своего осуществления прибегает к помощи себеподобного действия.

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

ЗАМЫКАНИЯ рулят - а без понимания рекурсии одними итерациями замыкания всего лиш продолжения :)

http://funcall.blogspot.ru/2011/02/no-stack-no-problem.html вкурчиво читани - заметка очень пользительна для понимания программирования.

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

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

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

ну мало-ли, что ты слышишь впервые? Ты попробуй использовать, и поймёшь. Отвёртка проще шуруповёрта. А чем проще закручивать шурупы? Я ведь не про «проще» в твоём каком-то смысле говорил, а про «проще», как «инструмент для формализации». Для этого машина Тьюринга более удобна ИМХО. Хотя это не принципиально, ибо они эквивалентны вообще говоря.

Я кстати сейчас нарыл инфу, которая какбэ проясняет

это не важно. brainfuck ещё новее и ещё «проще».

рекурсия же действие которое для своего осуществления прибегает к помощи себеподобного действия

Разве итерация не прибегает к тому-же? Возьмем простейший случай - нам надо пробежать по списку. итерация здесь прибегает к себеподобному действию - передвигается на одну позицию. Это эквивалентно некоей (сугубо рекурсивной) функции next:

(define next
  (lambda(lst do-staff)
    (if (not (null? lst))
      (begin
	(do-staff (car lst))
	(next (cdr lst) do-staff)))))

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

неа. Как инструмент — увы.

по сравнению с размером стэка, (почти) бесконечная.

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

Что и требовалось доказать

поймать меня хотел что-ли? Ну не получилось...

то не важно. brainfuck ещё новее и ещё «проще».

Да нет, это было предположение о том, что Тюнинг сп..л этот формализм у Поста. Машина поста как раз старше.
Что касается простоты, то отвертка проще для анализа закручивания шурупов, а не их закручивания, следуя твоей аналогии.

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

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

лениво искать.

вот вику почитай: http://ru.wikipedia.org/wiki/Итерация

поймать меня хотел что-ли? Ну не получилось...

Поймать?

Ты писал, что

В смысле? Всегда любую рекурсию можно переписать без оной.

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

А потом сам же пишешь, что можно.

Где там написано, что итерация не может выделять память?

Разве итерация не прибегает к тому-же?

Запили через итерацию Аккермана

рекурсия(если не концевая) ожидает завершения себеподобного дочернего вызова.

итерация == концевой которая не засирает стек ни ненужным хранением старых аргументов ни адрессами возврата по которым итак ретурны.

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

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

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

неверно. В рекурсии тоже есть условие. И тоже обычно в самом начале, как в цикле while.

например

unsigned f(unsigned n)
{
  if(n <= 1)
    return 1;
  else
    return f(n-1) * n;
}

он запилит - тока ручками упарится память под частично вычисленное менеджить

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

Я, кстати, склоняюсь к тому, что это было шагом назад, ибо цепочку контекстов мы можем создать легко, а вот first-class контексты потеряны.

ох лол.

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

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

Я как раз об этом и написал. Рекурсивен сам алгоритм, а итерация или «а-ля синтаксис рекурсии» - это уже детали.

шагом назад что?

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

или наоборот шаг назад , что идёт некоторый отказ от тотальности вложенности блоков и функций и идёт возврат «кактусных стеков»?

Итерация - это рекурсия, но рекурсия не всегда итерация.

как уже выше сказали - хорошо , что дошёл своим умом до примеров теории вычислимости.

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

чем рекурсивное погружение с возвратом .

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

Ну как, уже дошли до tail recursion?

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

а вот first-class контексты потеряны.

Параллели: объекты — замыкания, замкнутые переменные — private-поля. Замыкания можно костылить объектами или там тасканием указателей структурки-контексты. Это неудобно. Удобно, когда реализация языка сама посмотрит, какие свободные переменные используются, и засунет их в неявную анонимную структурку.

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

можно костылить объектами или там тасканием указателей структурки-контексты. Это неудобно.

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

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

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

тред не читал, оп-пост тоже: рекурсия более универсальна

Банально. Рекурсия позволяет выразить irreducible control flow, а итерация средствами исключительно структурного программирования не позволяет. Вот и вся разница. Рекурсия - это такой завуалированный goto, и подлежит уничтожению по той же причине, что и goto.

по сравнению с размером стэка, (почти) бесконечная.

бред. «Бесконечная» память тогда, и только тогда, когда _доказано_, что её размер не превысит её размера. Так бывает например если размер стека растёт не быстрее, чем log(N), причём стека больше чем log(N), где N — максимальное число объектов, которое возможно. Т.е. если мы храним 1048576 объектов макс(у нас их всего столько и/или больше просто не хватит кучи и/или больше не влезет в индекс/указатель), при этом стек у нас растёт как log2(n)(не более), при этом в стеке у нас как минимум места на 20 контекстов. Ну например в qsort при должной оптимизации размер стека растёт как раз не быстрее, чем log2(n), потому его обычно можно хранить в машинном стеке(т.к. для 4 миллиардов сортируемых эл-тов надо всего 32 кадра стека, а для 18446744073709551616 эл-тов всего 64)

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

А, это опять ты. Больной на всю голову ушлепок, который пытался доказывать, что ESP на x86 чем-то отличается от других регистров, и что доступ к «настоящему» стеку быстрее, чем доступ по смещению от другого регистра.

Да нет, это было предположение о том, что Тюнинг сп..л этот формализм у Поста. Машина поста как раз старше.

машина Тьюринга более общая ИМХО, а следовательно более универсальная.

Что касается простоты, то отвертка проще для анализа закручивания шурупов, а не их закручивания, следуя твоей аналогии.

угу. Анализ крутящего момента и оценка расхода энергии в дошираках будет конечно «проще», да...

Ну а вообще, я говорю — попробуй. ИМХО для меня было проще с машиной Тьюринга. А кто что у кого сп..л — мне поровну.

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

А потом сам же пишешь, что можно.

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

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

Тут всё зависит от числа вариантов m и шагов n. Если m^n небольшое число, то нет никакой нужды в рекурсии, и можно просто перебрать. Но вот я сейчас перебираю 196627050475552913618075908526912116283103450944214766927315415537966391196809 вариантов — fail. Сейчас пойду спать, и если решения не найдётся, придётся применить рекурсию, вместо итерации. Проблема в том, что я не знаю, сколько есть решений, но очевидно, что в первом миллиарде вариантов решений нет(уже перебрал), потому придётся наверное применить рекурсию, что-бы более экономно выбирать варианты. Рекурсия более «умная», т.к. я могу отсекать те пути, по которым я уже прошёл. Думаю, затратив несколько гигабайт памяти и несколько часов, я смогу просмотреть всё пространство решений, на что в итеративном варианте не хватит не только моей жизни, но и жизни всей вселенной...

Где там написано, что итерация не может выделять память?

а зачем для итерации дополнительная память? Есть формула для вычисления след. числа, что ещё надо? Ну вот например для вычисления 5! вовсе не обязательно вычислять 5,4,3,2,1 и потом перемножать, можно сразу умножать, потому достаточно памяти всего на 2 числа. Но если ты обходишь дерево, тебе нужно по одному биту на каждый поворот(для бинарного дерева, для тернарного уже 2 бита, точнее log2(3)), а таких поворотов столько, сколько высота дерева, а высота вообще говоря неизвестна, и может быть какой угодно.

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

итеративность идёт из «фортрана»

ЯП(в частности фортран) тут вообще не при чём.

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

это всё детали реализации, и не имеют отношения к вопросу. Gcc кстати сам контексты просчитывает, и если контекст не меняется, то gcc делает из рекурсии цикл, даже если рекурсия не хвостовая. При этом ты можешь писать обычные сишные переменные без всяких «замыканий», компилятор эти переменные сам находит. А эти ваши «замыкания» — прошлый век, и не нужно.

Кто тебе сказал, что каждая итерация должна вычислять число?

это всё детали реализации, и не имеют отношения к вопросу

Это непосредственно относится к языку. Или язык таков, что замыкания строятся автоматически, или все нужные переменные надо явно руками собирать и таскать. Реализация тут лишь при том, что это ей (в виде компилятора или интерпретатора) придётся выполнять данные действия.

Gcc кстати сам контексты просчитывает, и если контекст не меняется, то gcc делает из рекурсии цикл, даже если рекурсия не хвостовая.

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

А эти ваши «замыкания» — прошлый век, и не нужно.

Мы, видимо, говорим о разных вещах.

Кто тебе сказал, что каждая итерация должна вычислять число?

а что же она должна вычислять-то?

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

gcc умеет и часть контекста выдирать, а ХР она исключительно с неизменным оптимизируется вообще-то говоря. Т.е. в моём примере выше с факториалом совсем не ХР, но её gcc оптимизирует в итерации.

Мы, видимо, говорим о разных вещах.

а это и не тебе скорее написано.

да ты реанимировал вечноживой goto.

ну а почеснаку J-оператор Ландина и «ложки больше нет/небыло/небудет»

«фортранном» тут названо как яп так и вообще взгляд на ситуацию в которой чётко разделено сообщение которое обрабатывает и сообщение которое обрабатывают.

действие(изменение окружения) не есть число.

а зачем для итерации дополнительная память

То есть код

for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) res.append(seq[i);
}

не является итерацией? Ведь он выделяет память