Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 63
Отличный анализ, отличный вывод. Спасибо!
Понимание того, что стек вызовов — неконтролируемый (ну или плохо контролируемый) ресурс, к сожалению, отсутствует в головах у очень многих программистов. Те немногочисленные интервью, в которых мне довелось участвовать с обоих сторон, отлично это показали.
Понимание того, что стек вызовов — неконтролируемый (ну или плохо контролируемый) ресурс, к сожалению, отсутствует в головах у очень многих программистов. Те немногочисленные интервью, в которых мне довелось участвовать с обоих сторон, отлично это показали.
Просто начиная с момента «щелчка» в мозгах многих, когда достигается внезапное просветление в понимании что есть рекурсия, они помечают это знание как постигнутое… А на самом деле, это лишь пол дела.
Да ладно! Размер стека даже в С++ может быть не ограниченным (точнее ограниченным не более чем размер кучи). :-)
Вот только отдаст ли система твоему модулю неограниченный стек?
И, самое главное, получишь ли ты null при попытке рекурсии, аналогрично malloc/realloc?
И, самое главное, получишь ли ты null при попытке рекурсии, аналогрично malloc/realloc?
Ну, положим в случае юниксов я и для malloc скорее всего null не получу.
PS. А операционной системе про мой «стек» знать вовсе и не обязательно. См. например как это сделано в gcc.
PS. А операционной системе про мой «стек» знать вовсе и не обязательно. См. например как это сделано в gcc.
Да, кстати, это тоже поэма в семи лицах. «Как жить на пределе». Я её сейчас как раз пишу. В мае надеюсь выйдет на страницах хабрапечати.
Дык, разницы то почти и нет. :-) Что то не отловить что это. Точнее — отловится или нет, зависит от системы и желания отловить.
Например вот: stackoverflow.com/questions/199747/how-to-detect-possible-potential-stack-overflow-problems-in-a-c-c-program
Например вот: stackoverflow.com/questions/199747/how-to-detect-possible-potential-stack-overflow-problems-in-a-c-c-program
Почитайте про такую штуку как segmented stacks.
Для тех, кто программировал на ассемблере, ненадёжность рекурсии является очевидной.
«Recursion is the GOTO of functional programming»
Erik Meijer.
По моему опыты циклы и особенно map/fold часто читаемее, рекурсии для обработки коллекций.
Рекурсия: см. рекурсия.
Это не рекурсия, а бесконечный цикл.
К сожалению, Python не оптимизирует tail рекурсию — поэтому, считаю что на Python писать рекурсивные алгоритмы для прод систем не стоит.
Слова Гвидо на эту тему.
Слова Гвидо на эту тему.
В моём личном восприятии вселенной, польза от tail recursion optimization наличенствует только в функциональных языках без циклов для имитации этих самых циклов.
Во всех остальных случаях слишком легко малейшим изменением ТЗ сломать эту самую Tail рекурсию.
И тогда приходится изворачиваться и расшиперивать состояние, которое тащишь за собой через всю рекурсию, чтобы сохранить tail'овость.
Уж лучше просто избавиться от рекурсии и написать цикл явно.
Во всех остальных случаях слишком легко малейшим изменением ТЗ сломать эту самую Tail рекурсию.
И тогда приходится изворачиваться и расшиперивать состояние, которое тащишь за собой через всю рекурсию, чтобы сохранить tail'овость.
Уж лучше просто избавиться от рекурсии и написать цикл явно.
Последний раз когда использовал рекурсию, решал NP задачку на графах и не рекурсивного алгоритма с ходу не придумал.
Хороший повод выложить условие задачи и, возможно, решение, чтобы обезрекурсить её?
Задача: дан граф телефонной сети оператора. Узлы гафа АТС, ребра канал связи с которого можно собирать сигнальный трафик. Необходимо построить минимальное покрытие ребер, накрывающее все пути в графе.
Т.к. тех. директор отложил на неопределенное время, то дальше рабочего рекурсивного алгоритма не ушло.
Т.к. тех. директор отложил на неопределенное время, то дальше рабочего рекурсивного алгоритма не ушло.
А можно уточнить, все пути в графе, в смысле кратчайшие пути между всеми парами вершин? В такой формулировке придется всегда брать все ребра графа в покрытие, потому что каждое ребро есть кратчайший путь между двумя вершинами. Или граф взвешенный? Или покрыть надо пути между какими-то особыми вершинами?
Подождите, а чем это отличается от минимального остовного (покрывающего) дерева? Насколько я помню, в Кормане вполне себе дается итеративное решение задачи.
Особенность предметной области:
— статическая маршрутизация;
— балансировка каналов связи;
— аварии на каналах связи.
Т. е. трафик может пойди самым невообразимым путем и не пройти по ребру из остовного дерева.
На некоторых графах решением является множество ребер, которые не связаны общими вершинами, т. е. там могут не быть деревьев.
— статическая маршрутизация;
— балансировка каналов связи;
— аварии на каналах связи.
Т. е. трафик может пойди самым невообразимым путем и не пройти по ребру из остовного дерева.
На некоторых графах решением является множество ребер, которые не связаны общими вершинами, т. е. там могут не быть деревьев.
В любом случае, всегда можно попробовать эмулировать рекурсию: создать стек в куче и складывать туда старые значения переменных вместо ухода в глубь рекурсии. Это попрежнему будет есть память, но, по крайней мере, это будет память кучи а не стека.
Допустим, вот вам массив точек на двухмерной плоскости, у каждой точки соответственно 2 вещественные координаты. Они более менее все случайно сгенерированы. Нужно найти треугольник из точек наименьшей площади. Рекурсивно это делается как 2 пальца, а вот как циклами это сделать?
Рекурсивно как два пальца вы получите stack overflow. А с циклами это делается элементарно: создаём стек с нужными нам характеристиками и бегаем по массиву циклами. При этом, в качестве бонуса, мы получаем отсутствие необходимости пробрасывать состояния между вызовами функций и в любой момент можем легко посмотреть полное состояние стека.
Любая рекурсия может быть сведена к итерации над стеком (структурой данных). На практике так получаются более экономичные (в смысле потребления памяти) решения.
Рекурсия, по сути, это доказательство по индукции
Это утверждение неточно и вводит в заблуждение.
Рекурсия это сведение задачи сложности N к (N-1)
Например факториал F(N) = N * F(N-1)
Индукция это метод математического доказательства из двух этапов.
1. доказательство для базы ( обычно 1)
2. доказательство истинности для (N+1) при условии истинности для N
Насколько мне известно, любой рекурсивный алгоритм можно свести к нерекурсивному (но это не всегда просто ). Алгоритмы рекурсивные и нерекурсивные — разные алгоритмы.
Зачастую рекурсивные алгоритмы значительно элегантнее и проще для понимания, но в большинстве задач реализовывать надо стараться нерекурсивные.
С моей точки зрения рекурсия хороша в декларативных языках ( Лисп и т.д. )
Если поменять в индукции второй шаг на «доказательство истинности для N при условии истинности для N-1» отличие становится только косметическим. Или я делаю ту же ошибку, что и тонны других людей: неправильно понимаю, но при этом использую…
процитирую ВИКИПЕДИЮ
если вы считаете что по существу это одно и тоже ( метод доказательства = описанию ), то что лишнее?
ссылаться на других людей несколько некорректно, поскольку вы автор и отвечаете за свои слова.
Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.
Математическая индукция — метод математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
если вы считаете что по существу это одно и тоже ( метод доказательства = описанию ), то что лишнее?
ссылаться на других людей несколько некорректно, поскольку вы автор и отвечаете за свои слова.
В статье я говорю не о Рекурсивном Описании чего бы то ни было, а о Рекурсивных Алгоритмах, цель которых — решение задачи через решение аналогичных исходной подзадач.
Индуктивное доказательство 1-в-1 записывается в рекурсивной имплементации, именно в этой точки они и являются единым целым, именно о том, что не стоит использовать подобные наивные реализация и написана вся статья.
Индуктивное доказательство 1-в-1 записывается в рекурсивной имплементации, именно в этой точки они и являются единым целым, именно о том, что не стоит использовать подобные наивные реализация и написана вся статья.
Чем отличается рекурсивный алгоритм от рекурсивного описания?
Алгоритм ≈ описание последовательности действий.
Для меня индукция это доказательство путем предоставления рекурсивного алгоритма.
То есть мы доказываем истинность на практике — вот так оно решается, а значит, доказано.
Разумеется, это, опять же, только в ограниченной области, когда доказываем истинность, а не ложность.
Для меня индукция это доказательство путем предоставления рекурсивного алгоритма.
То есть мы доказываем истинность на практике — вот так оно решается, а значит, доказано.
Разумеется, это, опять же, только в ограниченной области, когда доказываем истинность, а не ложность.
индукция это доказательство путем предоставления рекурсивного алгоритма
если мы оба ведем речь о Математической индукции ( а не о электромагнитной, например ), то вы без какой либо необходимости переопределяете ее. Ваше мнение расходится с общепринятым.
«Индукция это метод математического доказательства из двух этапов.
1. доказательство для базы ( обычно 1)
2. доказательство истинности для (N+1) при условии истинности для N»
Рекурсия:
определяем шаг N через шаги для N-1
определяем базу.
где разница-то?
1. доказательство для базы ( обычно 1)
2. доказательство истинности для (N+1) при условии истинности для N»
Рекурсия:
определяем шаг N через шаги для N-1
определяем базу.
где разница-то?
Индукция это доказательство из двух этапов
Рекурсия это сведение (многократная редукция) задачи сложности N к (N-1) и далее
(N-1) к (N-2)
(N-2) к (N-3)
…
3 к 2
2 к 1
Выполняется (N-1) раз
Если вы не видите разницу между двумя разными понятиями, то я вам ничем не могу помочь.
Рекурсия это сведение (многократная редукция) задачи сложности N к (N-1) и далее
(N-1) к (N-2)
(N-2) к (N-3)
…
3 к 2
2 к 1
Выполняется (N-1) раз
Если вы не видите разницу между двумя разными понятиями, то я вам ничем не могу помочь.
Рекурсивный алгоритм записывается строго в том же виде, как и индуктивное доказательство.
Мы показываем как свести N к (N-1)
Мы говорим что делать при N=0 или N=1 или что там за базу.
То, что _выполняется_ оно все эти разы это уже другой вопрос.
В коде пишется строго сведение N к N-1 и поведение при базе.
Если вы не видите тут ничего общего, что ж, да, вы ничем не можете помочь.
Мы показываем как свести N к (N-1)
Мы говорим что делать при N=0 или N=1 или что там за базу.
То, что _выполняется_ оно все эти разы это уже другой вопрос.
В коде пишется строго сведение N к N-1 и поведение при базе.
Если вы не видите тут ничего общего, что ж, да, вы ничем не можете помочь.
У меня с некоторых пор есть яркий пример (по-мимо канонических и всем известных) где не надо использовать рекурсию, или если и использовать, то хвостовую.
Человек, выше меня по должности написал
А я переписал это на
Второй вариант позволяет обрабатывать связные списки с длиной более 60000 элементов и работает в трое быстрее то, что был изначально. Без замеров скорости мне не верили что я прав.
Человек, выше меня по должности написал
вот так:
public static void Reverse<T>(this LinkedList<T> list) {
list.Head = Reverse(list.Head);
}
private static LinkedList<T>.Node Reverse<T>(LinkedList<T>.Node node) {
if(node == null)
return null;
if(node.Next == null)
return node;
var next = node.Next;
node.Next = null;
var result = Reverse(next);
next.Next = node;
return result;
}А я переписал это на
это
public static void Reverse<T>(this LinkedList<T> list) {
if(list.Head == null)
return;
LinkedList<T>.Node first = list.Head;
LinkedList<T>.Node last = first;
LinkedList<T>.Node current = last.Next;
while(current != null) {
last.Next = current.Next;
current.Next = first;
first = current;
current = last.Next;
}
list.Head = first;
}
Второй вариант позволяет обрабатывать связные списки с длиной более 60000 элементов и работает в трое быстрее то, что был изначально. Без замеров скорости мне не верили что я прав.
Не очень понял, для кого рассчитана эта статья. На мой взгляд, новичок ничего не поймет (хотя бы потому, что нет четкого определения).
Для знакомого с рекурсией — зачем пример про обход дерева и числа фибонначи? Это же элементарно.
Про хвостовую рекурсию — ни слова
Множественная рекурсия, косвенная рекурсия — тоже не слышал.
Основная донесенная мысль, как я понял — рекурсия вредна, т.к.
1) внезапно может закончится стек и все сломается
2) есть более оптимальные нерекурсивные алгоритмы
Использование своего стека вместо стека вызовов — замечательно, только вот он тоже конечный и тоже может внезапно кончиться. Если подразумевается контролирование глубины рекурсии, не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.
Насчет оптимальности. Эту проблему решает динамическое программирование. В случае, когда разные ветки решают повторяющиеся подзадачи — разумеется, надо оптимизировать. Но это можно решить разными способами, не только переходом на нерекурсивный вариант.
Рекурсия зачастую существенно поднимает читаемость кода. Время программиста сейчас дороже, чем время процессора.
Мой пример задачи, которую муторно решать нерекурсивно — deepCopy для json, где в зависимости от типа object/array/primitive вызываются разные методы (пример косвенной и множественной рекурсии кстати).
Для знакомого с рекурсией — зачем пример про обход дерева и числа фибонначи? Это же элементарно.
Про хвостовую рекурсию — ни слова
Множественная рекурсия, косвенная рекурсия — тоже не слышал.
Основная донесенная мысль, как я понял — рекурсия вредна, т.к.
1) внезапно может закончится стек и все сломается
2) есть более оптимальные нерекурсивные алгоритмы
Использование своего стека вместо стека вызовов — замечательно, только вот он тоже конечный и тоже может внезапно кончиться. Если подразумевается контролирование глубины рекурсии, не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.
Насчет оптимальности. Эту проблему решает динамическое программирование. В случае, когда разные ветки решают повторяющиеся подзадачи — разумеется, надо оптимизировать. Но это можно решить разными способами, не только переходом на нерекурсивный вариант.
Рекурсия зачастую существенно поднимает читаемость кода. Время программиста сейчас дороже, чем время процессора.
Мой пример задачи, которую муторно решать нерекурсивно — deepCopy для json, где в зависимости от типа object/array/primitive вызываются разные методы (пример косвенной и множественной рекурсии кстати).
> не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.
Удачи протащить этот параметр через косвенную и множественную рекурсию, кстати ;) И учесть хвостовую.
Удачи протащить этот параметр через косвенную и множественную рекурсию, кстати ;) И учесть хвостовую.
На хвостовую это не должно влиять. В чем именно заключается проблема протаскивания через косвенную и множественную?
Проблема заключается в первую и основную очередь в том, что из абстракции начинают торчать уши реализации.
Причем торчать самым неприятным образом.
А еще максимальная глубина может зависеть от того, через какой из конкретных имплементаций шага проходит (в языках, где размер фрейма зависит от локальных переменных).
Причем торчать самым неприятным образом.
А еще максимальная глубина может зависеть от того, через какой из конкретных имплементаций шага проходит (в языках, где размер фрейма зависит от локальных переменных).
Позвольте тогда поинтересоваться, что в вашем понимании тогда «торчание ушей реализации» и как они не будут торчать в итеративной реализации.
Если вы говорите про то, что у функции будет лишний параметр — есть параметры по умолчанию или можно сделать обертку, если вас это так коробит в эстетическом плане.
Насчет максимальной глубины — да, зависит. А вы количество циклов ( размер стека) тоже ограничиваете в зависимости от сложности конкретного участка кода? Или выбираете какое-то разумное ограничение, которое не должно зависеть от реализации?
Если вы говорите про то, что у функции будет лишний параметр — есть параметры по умолчанию или можно сделать обертку, если вас это так коробит в эстетическом плане.
Насчет максимальной глубины — да, зависит. А вы количество циклов ( размер стека) тоже ограничиваете в зависимости от сложности конкретного участка кода? Или выбираете какое-то разумное ограничение, которое не должно зависеть от реализации?
По ограничениям позже. Это вообще скользкая дорожка где нет одного идеального решения.
А про торчание ушей — нет универсального рецепта, но таскание дополнительного параметра, который должны учитывать или как минимум не терять вторичные функции (в том числе, определяемые пользователем) это неприятно.
А про торчание ушей — нет универсального рецепта, но таскание дополнительного параметра, который должны учитывать или как минимум не терять вторичные функции (в том числе, определяемые пользователем) это неприятно.
Где таскание? В пользовательском коде? Этого можно избежать, и я сказал как. В коде функции? Два места — проверка (которая будет и в итеративном коде) и рекурсивный вызов (в итеративном подходе у вас будет инкремент счетчика ну или хотя бы декларация цикла).
О ужас, один лишний параметр. У вас этот «лишний» — счетчик. Там где напрашивается рекурсия, рекурсивный код будет компактнее (ваши же примеры это подтверждают) и, скорее всего, в нем будет меньше сущностей. Насчет этого я, надеюсь, вы согласитесь.
О ужас, один лишний параметр. У вас этот «лишний» — счетчик. Там где напрашивается рекурсия, рекурсивный код будет компактнее (ваши же примеры это подтверждают) и, скорее всего, в нем будет меньше сущностей. Насчет этого я, надеюсь, вы согласитесь.
А зачем в хвостовую рекурсию протаскивать глубину, если она будет развёрнута? Если же она развёрнута не будет — то и дополнительный индекс ни на что, кроме максимальной глубины, не повлияет.
А вы всегда знаете, будет ли ваша рекурсия развернута?
А в отладочном билде? А на новой версии компилятора?
А в отладочном билде? А на новой версии компилятора?
Если вы не знаете, будет ли развёрнута рекурсия — проще развернуть сразу вручную. Благо делается это тривиально: оборачиваем всё в цикл и перезаписываем значения переменных новыми в конце итерации.
Вот об этом я и пишу.
В этой ветке речь шла не о том, а о трудностях передачи уровня рекурсии в рекурсивную функцию.
И передавать параметр в хвостовую рекурсию не я собирался :P
Я просто обращаю внимание на то, что этот аргумент не состоятелен, так как такой тип рекурсии легче всех прочих раскрыть вручную. Не касаясь других типов рекурсии.
И передавать параметр в хвостовую рекурсию не я собирался :P
Я просто обращаю внимание на то, что этот аргумент не состоятелен, так как такой тип рекурсии легче всех прочих раскрыть вручную. Не касаясь других типов рекурсии.
Не смог уйти дальше первой строки топика.(( Расскажи кратко, в чём же суть?
В языке Scheme хвостовая рекурсия — кажется, единственный способ организовать цикл.
Помню, мучился, когда делал скрипт для Gimp, для массового применения набора фильтров к изображениям.
Помню, мучился, когда делал скрипт для Gimp, для массового применения набора фильтров к изображениям.
Ну упадёт воркер обрабатывающий запрос хакера — ничего страшного. Куда хуже, если он будет бесконечно крутиться в цикле, раздувая кучу. Избавляться от рекурсии нужно только если в штатной ситуации надо обрабатывать глубокие деревья, но это очень специфические случаи.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О бедной рекурсии замолвите слово, или всё, что вы не знали и не хотите о ней знать