Разница между рекурсивной функцией и использованием стека с точки зрения использования памяти

Question

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

Answer 1

Явная структура данных стека должна использовать немного меньше памяти в теории, поскольку рекурсивная функция всегда будет иметь дополнительные накладные расходы на вызов, для адреса возврата и т. Д.

Answer 2

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

Это представление поддерживается «Сборкой мусора быстро, но стек быстрее», Джеймс С. Миллери Гильермо Росаз: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.2789

Answer 3

Я предполагаю, что вы хотите обсудить разницу между двумя подходами одного и того же алгоритма. У нас есть график G = (V, E) , где V - это набор вершин, а E - это набор пар вершин, и мы запускаем Первый поиск (DFS) на графике:

• Использование рекурсивного подхода, при котором метод visit рекурсивно вызывает себя.
• Использование явного стека в цикле.

Оба метода в целом используют одинаковое количество места, O (d) , где d - глубина дерева поиска DFS (оно ограничено самым длинным возможные нециклические пути на графике.

Обычно явный стек использует немного меньше памяти, как пишет Пол Р. Другим важным моментом является то, что во многих языках стек вызовов функций строго ограничен и прервет программу, если он станет слишком большим. Явный стек, управляемый в куче, не представляет подобной проблемы. Чтобы получить немного меньше использования памяти, вы должны будете представлять стек как массив. Если вы представите его как связанный список, он, вероятно, не будет лучше. Это может быть даже немного хуже.