Рекурсия: см. рекурсия.
Все программисты делятся на 112 категорий: кто не понимает рекурсию, кто уже понял, и кто научился ею пользоваться. В общем, гурилка из меня исключительно картонный, так что постигать Дао Рекурсии тебе, читатель, всё равно придётся самостоятельно, я лишь постараюсь выдать несколько волшебных пенделей в нужном направлении.Прикладное программирование всегда занимается решением прикладных задач путем прикладывания усилий программиста для достижения результата в неидеальных условиях. Именно исходя из неидеальности этого мира и ограниченности ресурсов и складывается потребность в программистах: кому-то ведь надо помогать теоретикам упихать их стройную и красивую теорию в практику.
— Как она сложена?
— Превосходно! Только рука немного торчит из чемодана.
Именно пытаясь разместить стройную теорию алгоритма в жесткий рюкзак реальных ресурсов и приходится постоянно кроить по живому, перепаковывать, и вместо красивых и стройных определений Фибоначчи:
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
if n>1: return fib(n-1) + fib(n-2)
return n
приходится городить всевозможные грязные хаки, начиная от:
@memoized
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
if n>1: return fib(n-1) + fib(n-2)
return n
И заканчивая вообще:
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
n0 = 0
n1 = 1
for k in range(n):
n0, n1 = n1, n0+n1
return n0
Так что же такое рекурсия?
Рекурсия, по сути, это доказательство по индукции. Мы рассказываем, как получить результат для некоего состояния, предполагая что у нас есть результат для другого набора состояний, так же рассказываем, как получить результат в тех состояниях, к которым всё скатывается так или иначе.
Если вы ждете гостей и вдруг заметили на своем костюме пятно, не огорчайтесь. Это поправимо.
Например, пятна от растительного масла легко выводятся бензином. Пятна от бензина легко снимаются раствором щелочи.
Пятна от щелочи исчезают от уксусной эссенции. Следы от уксусной эссенции надо потереть подсолнечным маслом.
Ну, а как выводить пятна от подсолнечного масла, вы уже знаете...
Теперь давайте рассмотрим классический пример: обход дерева в глубину. Впрочем нет, давайте рассмотрим другой пример: нам надо распечатать дерево выражений в форме обратной польской записи. То есть для дерева 1 мы хотим напечатать «2 2 +» а для дерева 2 «2 2 + 2 2 + *».\begin{tikzpicture}
\node (is-root) {+}
child { node {2} }
child { node {2} };
\path (is-root) +(0,+0.5\tikzleveldistance)
node {\textit{Tree 1}};
\end{tikzpicture}
\begin{tikzpicture}
\node (is-root) {*}
child { node {+} [sibling distance=1cm] child {node{2}} child {node{2}} }
child { node {+} [sibling distance=1cm] child {node{2}} child {node{2}} };
\path (is-root) +(0,+0.5\tikzleveldistance)
node {\textit{Tree 2}};
\end{tikzpicture}
Как легко видеть, задача превращается в простой «обход дерева в глубину»: для каждого узла выводим содержимое всех его дочерних элементов, после чего выводим сам узел. То есть код будет:
class TreeNode(object):
def __init__(self, value=None, children=[]):
self.value = value
self.children = children
def printTree(node):
for child in node.children:
printTree(child)
print node.value,
def main():
tree1 = TreeNode("+", [ TreeNode(2), TreeNode(2) ])
tree2 = TreeNode("*", [ TreeNode("+", [ TreeNode(2), TreeNode(2) ]), TreeNode("+", [ TreeNode(2), TreeNode(2) ]) ])
print "Tree1:",
printTree(tree1)
print
print "Tree2:",
printTree(tree2)
print
if __name__ == "__main__":
main()
Казалось бы, всё отлично! Код прекрасно работает до тех пор, пока дерево соответствует требованиям: любой узел имеет массив детей (возможно пустой) и какое-либо значение. Кто скажет какое еще требование к этому дереву?
Не буду томить. Требование: не сильно большая глубина дерева. Как так? А вот как:
def buildTree(depth):
root = TreeNode("1")
node = root
for k in range(depth):
node = TreeNode("--", [ node ])
return node
def depthTest(depth):
tree = buildTree(depth)
print "Tree of depth", depth, ":",
printTree(tree)
def main():
for d in range(10000):
depthTest(d)
Запускаем, и ууупс! «Tree of depth 997: RuntimeError: maximum recursion depth exceeded». Лезем в документацию, и обнаруживаем функцию sys.getrecursionlimit. А теперь давайте отойдём от мира интерпретируемых языков, и перейдём в мир языков, которые запускаются прямо на процессоре. Например, на C++.
Мысленно перепишем 1-в-1 этот код на С++ (оставлю эту задачу читателю в качестве разминки), и попробуем найти предел, когда приложение упрется в ограничение…
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class TreeNode {
public:
string value_;
vector<TreeNode*> children_;
TreeNode(const string& value, const vector<TreeNode*>& children):
value_(value), children_(children) {}
virtual ~TreeNode() {}
};
void printTree(const TreeNode* node) {
for(auto i : node->children_)
printTree(i);
cout << node->value_ << " ";
}
TreeNode* buildTree(const int depth) {
auto root = new TreeNode("1", {});
auto node = root;
for(int i = 0; i<depth; i++) {
vector<TreeNode*> children;
children.push_back(node);
node = new TreeNode("--", children);
}
return node;
}
void depthTest(const int depth) {
auto tree = buildTree(depth);
cout << "Tree of depth " << depth << ": ";
printTree(tree);
cout << endl;
}
int main() {
for(int d=60000;; d+=16384) {
depthTest(d);
}
}
Запускаем… «Bus error (core dumped)». Судя по gdb, в момент падения стек глубиной 104790 фреймов. А что произойдёт, если мы захотим печатать не просто подряд через пробелы, а выводить еще "{" и "}" вокруг выражений? Ну то есть для дерева 1 чтобы результатом было {2 2 +} а для дерева 2 — {{2 2 +}{2 2 +}*}? Перепишем…
def printTree(node):
opened = False
for child in node.children:
if not opened:
print "{",
opened = True
printTree(child)
print node.value,
if opened:
print "}",
Ничего не изменилось, по прежнему падает при попытке распечатать дерево глубиной 997. А теперь то же самое, но на плюсах… Опа. Глубина стека при падении — 87327. Стоп. Мы всего-то добавили одну локальную переменную, никак не влияющую на алгоритм и суть происходящего, а предельный размер дерева сократился на 17%! А теперь самое весёлое — всё это сильно зависит от опций компилятора, от того, на какой платформе выполняется, в какой ОС и с какими настройками.
Но не это самое смешное. Давайте представим, что эту функцию использует другая функция. Всё хорошо, если она одна такая — мы можем подсчитать, на сколько же фактических шагов меньше максимальная глубина. А если эта функция используется из другой рекурсивной? Тогда возможности этой функции будут зависеть от глубины другой функции.
Вот таким образом наш прекрасный простой алгоритм перестаёт внезапно влезать в наш несовершенный чемодан. Предоставлю читателю самому представить как хорошо иметь подобные ограничения в сервисе, который запущен в продакшене и предоставляет некий сервис ничего не подозревающим хакерам, которые только и делают, что тычут в этот сервис своими грязными fuzzy тестерами.
Так в чем же проблема?
Использование рекурсивного алгоритма подразумевает использование практически не контролируемого ресурса: стека вызовов.
Во-1х, мы не можем точно знать сколько уже его использовано. Во-2х, мы не можем точно знать, сколько его еще осталось. В-3их мы не можем гарантировать доступность определённого размера этого ресурса к каждому вызову. В 4-ых, мы не можем фиксировать расход данного ресурса. Таким образом, мы попадаем в зависимость от ресурса, контролировать и распределять который чертовски сложно. В результате, мы не можем гарантировать каких либо характеристик данной функции/сервиса. Хорошо, если наш сервис работает в managed контексте: java, python, .net итп. Плохо, если сервис работает в неконтролируемой среде: javascript (с которым вообще всё плохо). Еще хуже, если сервис работает на C++, и глубина рекурсии зависит от данных, переданных пользователем.
Что же делать?
Если мы работаем не на микроконтроллере, о объёме стека можно не задумываться: для обычной цепочки вызовов его должно хватать. При условии, разумеется, что мы заботимся гигиене локальных переменных: большие объекты и массивы выделяются используя память (new/malloc). Однако использование рекурсии подразумевает, что вместо ограниченного количества вызовов, у нас их будет просто счетное.
Итак, чтобы избавиться от проблем, созданных рекурсией, можно сделать следующее (от простого к сложному):
— Жестко ограничить максимальный размер/формат/числа во входящих данных. Привет, zip бомбам и иже с ними — порой даже маленький входящий пакет может устроить большой переполох.
— Жестко ограничить максимальную глубину вызовов некоторым числом. Важно помнить, что это число должно быть ОЧЕНЬ небольшим. То есть порядка сотен. И обязательно добавить тесты, которые проверяют, что программа с этим максимальным числом не ломается. Причем с максимальным числом на всех возможных ветках исполнения (привет выделению локальных переменных по требованию). И не забывать проверять этот тест на разных опциях компилияции и после каждого билда.
— Жестко ограничить объём используемый стека. Используя сложные обходные маневры и знания о практической реализации исполнения в железе можно получить размер стека, который использован сейчас (типа взятия адреса локальной volatile переменной). В некоторых случаях (например, через libunwind в linux'е) можно получить так же доступный объём стека текущему потоку, и взять между ними разницу. При использовании подобного метода важно иметь тесты, проверяющие, что отсечение работает гарантированно и при всех вариантах входных данных — например, может получиться весело, если проверка идёт в одном методе, который рекурсивен через 3-4 других. И оно может упасть в промежуточном… Но только в режиме релиза, после inline'а некоторых функций, например. Впрочем, тут еще важны тесты на максимальную допустимую сложность, чтобы невзначай не отсечь часть корректных входных запросов, которыми клиенты реально пользуются.
— Лучший способ: избавиться от рекурсии.
И не лги, что ты волен и свят — Ты пленен и неволен.
Я раскрыл пред тобой небосвод!
Времена изменяют свой ход — Посмотри на ладони…
Беспредельная сладость свободы
Отринуть свободу
© Сергей Калугин
Да-да. После постижения Дао рекурсии постигаешь так же Дао отказа от рекурсии. Практически все рекурсивные алгоритмы имеют нерекурсивные аналоги. Начиная от более эффективных (см. выше Фибоначчи), и заканчивая эквивалентными, использующими очередь в памяти вместо стека вызовов.
Каноническая нерекурсивная реализацию обхода дерева в глубину:
def printTree(node):
stack = [ (node, False, False) ]
while len(stack)>0:
i = len(stack)-1
node, visited, opened = stack[i]
if not visited:
for child in reversed(node.children):
if not opened:
print "{",
opened = True
stack.append( (child, False, False) )
visited = True
stack[i] = (node, visited, opened)
else:
print node.value,
if opened:
print "}",
del stack[i]
Как легко видеть, алгоритм не изменился, но вместо использования стека вызовов используется массив stack, размещенный в памяти, и хранящий как контекст обработки (в нашем случае — флаг opened) так и контекст обработки (в нашем случае — до или после обработки детей). В случаях, когда нужно что-то делать между каждым из рекурсивных вызовов, либо добавляются фазы обработки. Обратите внимание: это уже оптимизированный алгоритм, складывающий всех детей в стек сразу, и именно поэтому складывающий в обратном порядке. Это гарантирует сохранение того же порядка, что и у исходного нерекурсивного алгоритма.
Вот этот же код, только написанный «в лоб», сохраняя контекст (заодно, выводящий запятые между элементами):
def printTree(node):
stack = [ (node, 0) ]
while len(stack)>0:
i = len(stack)-1
node, phase = stack[i]
if phase < len(node.children):
child = node.children[phase]
if phase == 0:
print "{",
if phase > 0:
print ",",
stack.append( (child, 0) )
stack[i] = (node, phase+1)
else:
print node.value,
if phase>0:
print "}",
del stack[i]
Да, переход на безрекурсивные технологии не совсем бесплатен: мы платим периодически более дорогим — динамическим выделением памяти для организации стека. Впрочем, это окупается: в «ручной стек» сохраняются не вообще все локальные переменные, а только минимально необходимый контекст, размер которого уже можно контролировать. Вторая статья расходов: читабельность кода. Код, записанный в нерекурсивном виде несколько сложнее для восприятия за счет ветвлений от текущего состояния. Решение этой проблемы лежит уже в области организации кода: вынесение шагов в отдельные функции и грамотное их наименование.
Злоключение
Несмотря на наличие некоего «налога на обезрекурсивание», я лично считаю его обязательным к уплате в любом месте, где идёт обработка данных, так или иначе поступивших от пользователя.
А как не используете рекурсию вы?
Комментарии (61)
DarthVictor
22.04.2015 11:51+3«Recursion is the GOTO of functional programming»
Erik Meijer.
По моему опыты циклы и особенно map/fold часто читаемее, рекурсии для обработки коллекций.
datacompboy Автор
22.04.2015 11:54+1Эээ… А зачем рекурсия для обработки коллекций?
tangro
23.04.2015 00:51Википедия говорит, что «Коллекции отличаются от контейнеров тем, что допускают ветвистую структуру». А где ветки — там и рекурсия.
HDDimon
22.04.2015 12:21+2К сожалению, Python не оптимизирует tail рекурсию — поэтому, считаю что на Python писать рекурсивные алгоритмы для прод систем не стоит.
Слова Гвидо на эту тему.datacompboy Автор
22.04.2015 12:27+2В моём личном восприятии вселенной, польза от tail recursion optimization наличенствует только в функциональных языках без циклов для имитации этих самых циклов.
Во всех остальных случаях слишком легко малейшим изменением ТЗ сломать эту самую Tail рекурсию.
И тогда приходится изворачиваться и расшиперивать состояние, которое тащишь за собой через всю рекурсию, чтобы сохранить tail'овость.
Уж лучше просто избавиться от рекурсии и написать цикл явно.HDDimon
22.04.2015 12:54Разделяю с вами ваше восприятие вселенной.
Одна из причин почему в Python нет tail recursion optimisation — невозможность иметь нормальный stack trace. В том же Erlang исследовать падение рекурсивной функции через stack trace еще то удовольствие.
RPG18
22.04.2015 12:23+2Последний раз когда использовал рекурсию, решал NP задачку на графах и не рекурсивного алгоритма с ходу не придумал.
datacompboy Автор
22.04.2015 12:24Хороший повод выложить условие задачи и, возможно, решение, чтобы обезрекурсить её?
RPG18
22.04.2015 13:16Задача: дан граф телефонной сети оператора. Узлы гафа АТС, ребра канал связи с которого можно собирать сигнальный трафик. Необходимо построить минимальное покрытие ребер, накрывающее все пути в графе.
Т.к. тех. директор отложил на неопределенное время, то дальше рабочего рекурсивного алгоритма не ушло.
wataru
22.04.2015 14:01А можно уточнить, все пути в графе, в смысле кратчайшие пути между всеми парами вершин? В такой формулировке придется всегда брать все ребра графа в покрытие, потому что каждое ребро есть кратчайший путь между двумя вершинами. Или граф взвешенный? Или покрыть надо пути между какими-то особыми вершинами?
Halt
22.04.2015 14:17+2Подождите, а чем это отличается от минимального остовного (покрывающего) дерева? Насколько я помню, в Кормане вполне себе дается итеративное решение задачи.
RPG18
22.04.2015 15:57Особенность предметной области:
— статическая маршрутизация;
— балансировка каналов связи;
— аварии на каналах связи.
Т. е. трафик может пойди самым невообразимым путем и не пройти по ребру из остовного дерева.
На некоторых графах решением является множество ребер, которые не связаны общими вершинами, т. е. там могут не быть деревьев.
ulis
22.04.2015 21:36Попробуйте ещё какую-нибудь хорошую метаэвристику типа Harmony Search, раз такой ад.
Krypt
22.04.2015 15:56В любом случае, всегда можно попробовать эмулировать рекурсию: создать стек в куче и складывать туда старые значения переменных вместо ухода в глубь рекурсии. Это попрежнему будет есть память, но, по крайней мере, это будет память кучи а не стека.
RPG18
22.04.2015 16:05+1Легко сказать, сложно сделать, да и зачем? Наша компания зарабатывает за счет оказания тех поддержки, поэтому нам известны графы реальных сетей и в них нет какого то гигантского количества вершин и ребер. ПО крутится на серверах под GLU/Linux и мы всегда можем расширить стек.
ababo
22.04.2015 13:59+1Любая рекурсия может быть сведена к итерации над стеком (структурой данных). На практике так получаются более экономичные (в смысле потребления памяти) решения.
datacompboy Автор
22.04.2015 14:00Но еще есть немало алгоритмов, которые просто имеют нерекурсивный аналог, более эффективный.
… хотя поиск оптимального пути в графе по-моему все же «лобовая» задача.RPG18
22.04.2015 20:18А как это вы свели задачу к поиску оптимального пути?
datacompboy Автор
22.04.2015 21:12+1После уточнений вверху это уже не оптимальный путь. Я пока вообще не понимаю задачу, поэтому жду еще уточнений :)
SemenovVV
22.04.2015 13:20+2Рекурсия, по сути, это доказательство по индукции
Это утверждение неточно и вводит в заблуждение.
Рекурсия это сведение задачи сложности N к (N-1)
Например факториал F(N) = N * F(N-1)
Индукция это метод математического доказательства из двух этапов.
1. доказательство для базы ( обычно 1)
2. доказательство истинности для (N+1) при условии истинности для N
Насколько мне известно, любой рекурсивный алгоритм можно свести к нерекурсивному (но это не всегда просто ). Алгоритмы рекурсивные и нерекурсивные — разные алгоритмы.
Зачастую рекурсивные алгоритмы значительно элегантнее и проще для понимания, но в большинстве задач реализовывать надо стараться нерекурсивные.
С моей точки зрения рекурсия хороша в декларативных языках ( Лисп и т.д. )datacompboy Автор
22.04.2015 13:44Если поменять в индукции второй шаг на «доказательство истинности для N при условии истинности для N-1» отличие становится только косметическим. Или я делаю ту же ошибку, что и тонны других людей: неправильно понимаю, но при этом использую…
SemenovVV
22.04.2015 14:16+1процитирую ВИКИПЕДИЮ
Реку?рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.
Математическая индукция — метод математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
если вы считаете что по существу это одно и тоже ( метод доказательства = описанию ), то что лишнее?
ссылаться на других людей несколько некорректно, поскольку вы автор и отвечаете за свои слова.datacompboy Автор
22.04.2015 14:30В статье я говорю не о Рекурсивном Описании чего бы то ни было, а о Рекурсивных Алгоритмах, цель которых — решение задачи через решение аналогичных исходной подзадач.
Индуктивное доказательство 1-в-1 записывается в рекурсивной имплементации, именно в этой точки они и являются единым целым, именно о том, что не стоит использовать подобные наивные реализация и написана вся статья.SemenovVV
22.04.2015 15:07Чем отличается рекурсивный алгоритм от рекурсивного описания?
datacompboy Автор
22.04.2015 15:14-1Алгоритм ? описание последовательности действий.
Для меня индукция это доказательство путем предоставления рекурсивного алгоритма.
То есть мы доказываем истинность на практике — вот так оно решается, а значит, доказано.
Разумеется, это, опять же, только в ограниченной области, когда доказываем истинность, а не ложность.SemenovVV
22.04.2015 16:14индукция это доказательство путем предоставления рекурсивного алгоритма
если мы оба ведем речь о Математической индукции ( а не о электромагнитной, например ), то вы без какой либо необходимости переопределяете ее. Ваше мнение расходится с общепринятым.datacompboy Автор
22.04.2015 16:35«Индукция это метод математического доказательства из двух этапов.
1. доказательство для базы ( обычно 1)
2. доказательство истинности для (N+1) при условии истинности для N»
Рекурсия:
определяем шаг N через шаги для N-1
определяем базу.
где разница-то?SemenovVV
22.04.2015 17:29-1Индукция это доказательство из двух этапов
Рекурсия это сведение (многократная редукция) задачи сложности N к (N-1) и далее
(N-1) к (N-2)
(N-2) к (N-3)
…
3 к 2
2 к 1
Выполняется (N-1) раз
Если вы не видите разницу между двумя разными понятиями, то я вам ничем не могу помочь.datacompboy Автор
22.04.2015 18:25-1Рекурсивный алгоритм записывается строго в том же виде, как и индуктивное доказательство.
Мы показываем как свести N к (N-1)
Мы говорим что делать при N=0 или N=1 или что там за базу.
То, что _выполняется_ оно все эти разы это уже другой вопрос.
В коде пишется строго сведение N к N-1 и поведение при базе.
Если вы не видите тут ничего общего, что ж, да, вы ничем не можете помочь.
T-D-K
22.04.2015 14:32-2У меня с некоторых пор есть яркий пример (по-мимо канонических и всем известных) где не надо использовать рекурсию, или если и использовать, то хвостовую.
Человек, выше меня по должности написалвот так: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; }
ov7a
22.04.2015 17:06+9Не очень понял, для кого рассчитана эта статья. На мой взгляд, новичок ничего не поймет (хотя бы потому, что нет четкого определения).
Для знакомого с рекурсией — зачем пример про обход дерева и числа фибонначи? Это же элементарно.
Про хвостовую рекурсию — ни слова
Множественная рекурсия, косвенная рекурсия — тоже не слышал.
Основная донесенная мысль, как я понял — рекурсия вредна, т.к.
1) внезапно может закончится стек и все сломается
2) есть более оптимальные нерекурсивные алгоритмы
Использование своего стека вместо стека вызовов — замечательно, только вот он тоже конечный и тоже может внезапно кончиться. Если подразумевается контролирование глубины рекурсии, не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.
Насчет оптимальности. Эту проблему решает динамическое программирование. В случае, когда разные ветки решают повторяющиеся подзадачи — разумеется, надо оптимизировать. Но это можно решить разными способами, не только переходом на нерекурсивный вариант.
Рекурсия зачастую существенно поднимает читаемость кода. Время программиста сейчас дороже, чем время процессора.
Мой пример задачи, которую муторно решать нерекурсивно — deepCopy для json, где в зависимости от типа object/array/primitive вызываются разные методы (пример косвенной и множественной рекурсии кстати).
datacompboy Автор
22.04.2015 17:13-2> не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.
Удачи протащить этот параметр через косвенную и множественную рекурсию, кстати ;) И учесть хвостовую.ov7a
22.04.2015 17:25+3На хвостовую это не должно влиять. В чем именно заключается проблема протаскивания через косвенную и множественную?
datacompboy Автор
22.04.2015 18:27Проблема заключается в первую и основную очередь в том, что из абстракции начинают торчать уши реализации.
Причем торчать самым неприятным образом.
А еще максимальная глубина может зависеть от того, через какой из конкретных имплементаций шага проходит (в языках, где размер фрейма зависит от локальных переменных).ov7a
22.04.2015 19:15Позвольте тогда поинтересоваться, что в вашем понимании тогда «торчание ушей реализации» и как они не будут торчать в итеративной реализации.
Если вы говорите про то, что у функции будет лишний параметр — есть параметры по умолчанию или можно сделать обертку, если вас это так коробит в эстетическом плане.
Насчет максимальной глубины — да, зависит. А вы количество циклов ( размер стека) тоже ограничиваете в зависимости от сложности конкретного участка кода? Или выбираете какое-то разумное ограничение, которое не должно зависеть от реализации?datacompboy Автор
22.04.2015 19:42По ограничениям позже. Это вообще скользкая дорожка где нет одного идеального решения.
А про торчание ушей — нет универсального рецепта, но таскание дополнительного параметра, который должны учитывать или как минимум не терять вторичные функции (в том числе, определяемые пользователем) это неприятно.ov7a
22.04.2015 23:20Где таскание? В пользовательском коде? Этого можно избежать, и я сказал как. В коде функции? Два места — проверка (которая будет и в итеративном коде) и рекурсивный вызов (в итеративном подходе у вас будет инкремент счетчика ну или хотя бы декларация цикла).
О ужас, один лишний параметр. У вас этот «лишний» — счетчик. Там где напрашивается рекурсия, рекурсивный код будет компактнее (ваши же примеры это подтверждают) и, скорее всего, в нем будет меньше сущностей. Насчет этого я, надеюсь, вы согласитесь.
Krypt
22.04.2015 17:35+2А зачем в хвостовую рекурсию протаскивать глубину, если она будет развёрнута? Если же она развёрнута не будет — то и дополнительный индекс ни на что, кроме максимальной глубины, не повлияет.
datacompboy Автор
22.04.2015 18:28А вы всегда знаете, будет ли ваша рекурсия развернута?
А в отладочном билде? А на новой версии компилятора?Krypt
22.04.2015 18:32Если вы не знаете, будет ли развёрнута рекурсия — проще развернуть сразу вручную. Благо делается это тривиально: оборачиваем всё в цикл и перезаписываем значения переменных новыми в конце итерации.
datacompboy Автор
22.04.2015 18:33+1Вот об этом я и пишу.
Krypt
22.04.2015 18:41В этой ветке речь шла не о том, а о трудностях передачи уровня рекурсии в рекурсивную функцию.
И передавать параметр в хвостовую рекурсию не я собирался :P
Я просто обращаю внимание на то, что этот аргумент не состоятелен, так как такой тип рекурсии легче всех прочих раскрыть вручную. Не касаясь других типов рекурсии.
dcc0
23.04.2015 10:27В языке Scheme хвостовая рекурсия — кажется, единственный способ организовать цикл.
Помню, мучился, когда делал скрипт для Gimp, для массового применения набора фильтров к изображениям.datacompboy Автор
23.04.2015 11:04То же и в Erlang.
Но вообще, правильное решение — пользуйте fold'ы :)HDDimon
23.04.2015 11:19Fold в Erlang тоже не всегда применим, особенно когда у вас вложенные fold с ветвистой логикой. Tail рекурсия в данном случае выглядит гораздо чище.
vintage
24.04.2015 10:24+1Ну упадёт воркер обрабатывающий запрос хакера — ничего страшного. Куда хуже, если он будет бесконечно крутиться в цикле, раздувая кучу. Избавляться от рекурсии нужно только если в штатной ситуации надо обрабатывать глубокие деревья, но это очень специфические случаи.
23derevo
Отличный анализ, отличный вывод. Спасибо!
Понимание того, что стек вызовов — неконтролируемый (ну или плохо контролируемый) ресурс, к сожалению, отсутствует в головах у очень многих программистов. Те немногочисленные интервью, в которых мне довелось участвовать с обоих сторон, отлично это показали.
datacompboy Автор
Просто начиная с момента «щелчка» в мозгах многих, когда достигается внезапное просветление в понимании что есть рекурсия, они помечают это знание как постигнутое… А на самом деле, это лишь пол дела.
valexey
Да ладно! Размер стека даже в С++ может быть не ограниченным (точнее ограниченным не более чем размер кучи). :-)
datacompboy Автор
Вот только отдаст ли система твоему модулю неограниченный стек?
И, самое главное, получишь ли ты null при попытке рекурсии, аналогрично malloc/realloc?
valexey
Ну, положим в случае юниксов я и для malloc скорее всего null не получу.
PS. А операционной системе про мой «стек» знать вовсе и не обязательно. См. например как это сделано в gcc.
datacompboy Автор
Да, кстати, это тоже поэма в семи лицах. «Как жить на пределе». Я её сейчас как раз пишу. В мае надеюсь выйдет на страницах хабрапечати.
valexey
Дык, разницы то почти и нет. :-) Что то не отловить что это. Точнее — отловится или нет, зависит от системы и желания отловить.
Например вот: stackoverflow.com/questions/199747/how-to-detect-possible-potential-stack-overflow-problems-in-a-c-c-program
Halt
Почитайте про такую штуку как segmented stacks.
datacompboy Автор
Знаю. И по-прежнему остаётся открытый вопрос о поимке ограничения.
evtomax
Для тех, кто программировал на ассемблере, ненадёжность рекурсии является очевидной.