Как избежать рекурсивной функции?

Ответ 1

Нет никакого переносного решения, кроме как путем замены рекурсии с явным управлением стеком (используя std::vector<Node*>). Непереносимо вы можете отслеживать глубину с использованием статической переменной; если вы знаете максимальный стек размер и размер стека каждой рекурсии, тогда вы можете убедитесь, что глубина не превышает этого.

Многие системы, такие как Linux и Solaris, не могут знать максимальная глубина стека вверх, так как стек выделен динамически. По крайней мере, в Linux и Solaris, однако, один раз память была выделена стеку, она останется выделенной и остаются затронутыми в стеке. Таким образом, вы можете глубоко в начале программы (возможно, сбой, но прежде чем что-либо сделать), а затем проверить это значение позже:

static char const* lowerBound = nullptr;

//  At start-up...
void
preallocateStack( int currentCount ) {
{
    char dummyToTakeSpace[1000];
    -- currentCount;
    if ( currentCount <= 0 ) {
        lowerBound = dummyToTakeSpace;
    } else {
        preallocateStack( currentCount - 1 );
    }
}

void
checkStack()
{
    char dummyForAddress;
    if ( &dummyForAddress < lowerBound ) {
        throw std::bad_alloc();   //  Or something more specific.
    }
}

Вы заметите, что есть несколько случаев undefined/неопределенное поведение, плавающее в этом коде, но Я использовал его успешно несколько раз (под Solaris на Sparc, но Linux на ПК работает точно так же в этом отношение). Фактически, он будет работать практически в любой системе, где: - стек растет, и - локальные переменные выделяются в стеке. Таким образом, он также будет работать на Windows, но если он не сможет выделите исходный стек, вам придется переписываться, а не просто запустите программу в тот момент, когда меньше активности на (или изменить ulimits) (поскольку размер стека в Windows фиксируется во время соединения).

EDIT:

Один комментарий относительно использования явного стека: некоторые системы (включая Linux, по умолчанию) overcommit, что означает что вы не можете надежно получить ошибку из памяти, когда расширение std::vector<>; система сообщит std::vector<>, что память есть, а затем дать запрограммируйте нарушение сегмента при попытке получить к нему доступ.

Ответ 2

рассмотрите итерацию по рекурсии, если это действительно проблема.

http://en.wikipedia.org/wiki/Tree_traversal

см. код psedo для итерации iterativeInorder iterativePreorder iterativePostorder

В основном используйте свой собственный список как структуру данных стека в цикле while, вы можете эффективно заменить рекурсию функции.

Ответ 3

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

Я вижу ваш "if() return;" и поэтому вы должны избегать бесконечных циклов, так как каждая ветвь вашего дерева заканчивается нулем. Таким образом, одна из возможностей - неправильный ввод, когда какая-либо ветвь дерева никогда не достигает нуля. (Это произойдет, например, если у вас есть петля в структуре данных дерева.)

Единственная другая возможность, которую я вижу, это то, что ваша структура данных дерева просто слишком велика для объема доступной памяти стека. (N.B. это виртуальная память, и пространство подкачки может быть использовано, поэтому это не обязательно проблема нехватки ОЗУ.) Если это произойдет, вам может потребоваться какой-то другой алгоритмический подход, который не является рекурсивным. Хотя ваша функция имеет небольшой объем памяти, поэтому, если вы не пропустили какую-либо дополнительную обработку, которую она делает, ваше дерево действительно должно быть ДЕЙСТВИТЕЛЬНО ГЛУБОКО, чтобы это было проблемой. (N.B. это максимальная глубина, что проблема здесь, а не общее количество узлов.)

Ответ 4

Вы можете увеличить размер стека для своей ОС. Обычно это настраивается через ulimit, если вы находитесь в среде, подобной Unix.

например. на Linux вы можете сделать ulimit -s unlimited, который установит размер стека на "неограниченный", хотя у IIRC есть жесткий предел, и вы не можете посвятить всю свою память одному процессу (хотя в одном из ответов в ссылках ниже упоминается неограниченный количество).

Мои предложения состоят в том, чтобы запустить ulimit -s, который предоставит вам текущий размер стека, и если вы все равно получите переполнение стека вдвое, пока не получите удовольствие.

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

Ответ 5

Если у вас очень большое дерево, и вы сталкиваетесь с проблемами с обходом стека с помощью рекурсивных обходов, проблема в том, что у вас нет сбалансированного дерева. Первое предложение - попробовать сбалансированное двоичное дерево, такое как дерево красного дерева или дерево AVL, или дерево с более чем двумя детьми на node, например дерево B+. Библиотека С++ предоставляет std::map<> и std::set<>, которые обычно реализуются с использованием сбалансированного дерева.

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

n = find_first(n);
while (! is_null(n)) {
    n->print();
    if (n->is_leaf()) n = n->r;
    else n = find_first(n->r);
}

Ответ 6

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

Ответ 7

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

Недостаток: это решение происходит за счет накладных расходов переменной int, выделяемой для каждого node.

void inorder(node* n,int counter)
{
 if(counter<limit) //limit specified as per system limit
 {
  if(n == null) return;
  inorder(n->l,counter-1);
  n->print();
  inorder(n->r,counter-1);
 }
 else
  n->print();
}

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