На днях я пытался решить проблему, связанную с древовидной структурой данных. Обычно большинство решений проблем, связанных с деревьями / графами, носят рекурсивный характер.
Рекурсия предполагает использование неявных стеков. Это реализуется в фоновом режиме компилятором, который используется для компиляции вашего кода.
Этот фоновый стек, созданный компилятором, известен как « Стек вызовов ». Википедия определяет стек вызовов как стек структуру данных, в которой хранится информация об активных подпрограммах компьютерной программы. У него есть и другие названия, такие как стек времени выполнения, но это наиболее распространенное.
Каждый вызов функции / подпрограммы использует фрейм внутри стека вызовов, который называется фрейм стека. Когда функция возвращает значение, ее кадр стека извлекается из стека вызовов.
Это заставило меня задуматься, а что, если бы я реализовал свой собственный явный стек для решения проблемы вместо того, чтобы использовать рекурсию для выполнения задачи за меня? Какие компромиссы?
Переполнение стека
Принципиальное различие между двумя стеками состоит в том, что пространство, выделяемое компилятором для стека вызовов программы, является фиксированным. Это означает, что произойдет переполнение стека, если вы не уверены в максимальном значении «нет». ожидаемых рекурсивных вызовов функций и слишком много вызовов, чем пространство, выделенное для стека, может обработать в данный момент времени.
С другой стороны, если вы определяете явный стек, он реализуется в пространстве кучи, выделенном программе компилятором во время выполнения. И угадайте, размер кучи не фиксирован и может динамически увеличиваться во время выполнения, когда это необходимо. Вам действительно не нужно беспокоиться о явном переполнении стека. Это хорошо для масштабируемости и управления неизбежными крайними случаями, когда есть глубокие рекурсивные вызовы.
Пространство и время
Какой из них будет быстрее в данной ситуации?
Итерация в явном стеке может быть быстрее, чем рекурсия в языках, которые не поддерживают оптимизацию, связанную с рекурсией, например оптимизацию хвостового вызова для хвостовой рекурсии.
Что такое T рекурсия?
Хвостовая рекурсия - это частный случай рекурсии, когда рекурсивная функция больше не выполняет вычислений после вызова рекурсивной функции, то есть последний шаг функции - это вызов рекурсивной функции.
Что такое Дополнительная оптимизация (TCO)?
Оптимизация хвостового вызова - это когда вы можете избежать выделения нового кадра стека для функции, потому что вызывающая функция просто вернет значение, которое она получает от вызываемой функции.
Таким образом, компиляторы / языки, поддерживающие оптимизацию хвостового вызова, реализуют вызов рекурсивной функции только с одним кадром стека в стеке вызовов. Если ваш компилятор / язык не поддерживает это, то использование явного стека сэкономит вам МНОГО места и времени.
Python не поддерживает оптимизацию хвостового вызова. Основная причина этого - наличие полной и четкой трассировки стека, которая обеспечивает эффективную отладку.
Практически все компиляторы C / C ++ поддерживают оптимизацию хвостового вызова.
Интуиция
Некоторым людям очень трудно представить себе рекурсивное решение. Просто он когнитивно не щелкает. Иногда явное управление стеком помогает упростить работу при использовании нескольких параметров.
С другой стороны, рекурсивное решение значительно уменьшает размер исходного кода и делает его более удобным в обслуживании.
Вывод
В конце концов, однозначного ответа нет. Для конкретного сценария необходимо учитывать множество факторов, таких как масштабируемость, ремонтопригодность кода, используемый язык / компилятор и т. Д.
Лучшим способом было бы реализовать решение обоими способами, рассчитав 2 решения на входном наборе и проанализировав пиковое использование пространства перед его развертыванием в производственной установке.
