память и глубина (относительно ширины) рекурсии в c

Question

У меня есть два вопроса, связанных с памятью. Сначала немного предыстории. Я начинающий программист.

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

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

Теперь вопрос.

(а) Мне нужно написать другие функции, которые, очевидно, просты и понятны, если написаны с использованием чистой рекурсии. Я вижу, как это можно было бы написать итеративно. Это не сложно, просто утомительно. Максимальная глубина моих деревьев будет 3-5, однако количество узлов на каждом уровне велико. Насколько я понимаю, каждый рекурсивный вызов будет хранить адреса в стеке. Если глубина велика, может не хватить памяти. Но если глубина мала, наказание (память / скорость) за использование рекурсивной функции может быть не страшным.

Есть ли у людей рекомендации по критериям для принятия решения, является ли предпочтительным итеративное / рекурсивное решение? Я читал различные темы на сайте об итеративных решениях, но не смог найти ничего, что прямо говорит об этой проблеме.

(b) Во-вторых, вопрос касается запроса памяти у системы. Я знаю, что некоторые приложения могут запрашивать определенный объем памяти. Я использую mingw-gcc4.x с IDE Netbeans. Как указать максимальный объем памяти, который программа может использовать в режиме отладки / выпуска? Или же это зависит исключительно от доступной оперативной памяти и не требует явных спецификаций?!

Заранее спасибо,

paras

~ RT

Answer 1

"Максимальная глубина моих деревьев будет 3-5"

Эта глубина рекурсии не повлияет на размер стека по умолчанию для любой версии Windows или любой другой системы, которую вы когда-либо увидите, у которой нет "Осторожно! Стек крошечный!" намазанный всем этим. Большинство программ выполняют более 3-5 вызовов без какой-либо рекурсии.

Так что, пока ваша рекурсия идет только «вниз» по вашему дереву, а не «поперек» его ширины, вы в порядке. Если, конечно, вы не делаете что-то действительно необычное, например, помещаете огромный массив в стек как локальную переменную.

Прав ли я, что ваша (после заказа) рекурсия выглядит примерно так?

void doNode(struct node *n) {
    for (int i = 0; i < n->num_nodes; ++i) {
        doNode(n->nodes[i]);
    }
    // do some work on this node
}

Если это так, то для 3-5 уровней он будет использовать только один стек: если он выглядит так:

void doNode(struct node *n) {
    int myRidiculousArray[100*1000] = { 0 };
    for (int i = 0; i < n->num_nodes; ++i) {
        doNode(n->nodes[i]);
    }
    // do some work on this node, using myRidiculousArray
}

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

Answer 2

Даже итеративная реализация является рекурсивным алгоритмом, если вы используете стек для хранения узлов; оба используют пространство O (f), где «f» - это функция, которая «больше», чем константа (c - это O (f), но f - это не O (1)). Вы можете по-прежнему использовать меньше памяти с итеративной версией, если элементы вашего стека меньше фрейма стека вызовов. Если это так, вы можете уменьшить размер стека вызовов, используя замыкания, предполагая, что язык поддерживает их.

Итерационные алгоритмы будут иметь O (1) требований к пространству. Как отмечает Дашогун, даже рекурсивная реализация может достичь этого с помощью хвостовых вызовов.

Потратьте немного времени, пытаясь найти итерационный алгоритм. Если вы не можете найти его, я рекомендую перейти к рекурсивной реализации, если вы не уверены наверняка, что вам нужно обрабатывать рекурсивную структуру, которая (в наши дни) имеет глубину не менее 2 ¹³ . Для двоичного дерева это 2 ^{2 13} узлов, которые, я очень сильно сомневаюсь, вы увидите.

Answer 3

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

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

Answer 4

а) Рекурсия сама по себе неплоха. Однако если запись итеративного алгоритма близка по сложности, вы должны использовать итеративный. Перед принятием рекурсивного алгоритма необходимо выполнить некоторые предварительные условия:

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

(b) Если вы спрашиваете о размере стека: я вижу, вы используете mingw, поэтому вы, вероятно, собираете для Windows. Размер стека в Windows - на поток. Посмотрите здесь как настроить зарезервированный и изначально зафиксированный размер стека.

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