Интервью на стеке

Question

недавно мой друг посетил intv, он столкнулся с этим вопросом (интервьюер придумал это из ответа моего друга на другой вопрос) Скажем, у нас есть возможность использовать либо 1) рекурсия -> использует системный стек, я думаю, что ОС заботится обо всем 2) использовать наш собственный стек только для части данных и добиться цели. что-то исправить. Какой из них вы предпочитаете? и почему? предположим, что размер стека не превысит 100.

Answer 1

Я бы использовал системный стек. Зачем заново изобретать колесо?

Answer 2

Зависит от алгоритма.Малое использование стека, системный стек.Нужно много стека, иди в кучу.Размер стека ограничен ОС, после которой ОС выбрасывает stackoverflow ;-) Если алгоритм использует больше места в стеке, то я бы использовал структуру данных стека и поместил бы данные в кучу

Answer 3

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

• рекурсия обычно избегает явного цикла
• рекурсия иногда может просто использовать локальные переменные внутри функции, чтобы избежать сохранения в контейнере результатов, так как они вычисляются
• рекурсия может сделать тривиальным изменение порядка, в которомПодводные результаты собираются
• рекурсия означает, что есть предел глубины обрабатываемой информации, где - как часто реализация цикла легко этого избегает, или, по крайней мере, имеет требования к памяти, которые более точно отражают потребности обработки данных
  • чем более широко применимо ваше программное обеспечение, тем важнее устранение произвольных ограничений (например, программное обеспечение UNIX, такое как modern vim, less, GNU grep и т. Д., Делает минимальные предположения о длине файла / строки / выраженияи динамически пытаться шо чем бы их ни спрашивали / многие здесь будут помнить старые редакторы и специфичные для поставщика утилиты, например, grep одной «небесной» компании, который никогда не совпадет с результатами в конце слишком длинной строки, редакторы, которые SIGSEGVed, выключаются, повреждены или замедлены вбесполезность в длинных строках или файлах)
• наивная рекурсия может привести к невероятно неэффективным комбинированным подрежимам
• некоторые люди находят рекурсию легче для понимания, а некоторые - труднее - определенноэто подходит, как мы думаем о некоторых проблемах лучше, чем другие

Answer 4

Чаще всего простота лучше, чем небольшой прирост производительности.

Не перебивайте решение и не теряйте удобочитаемость / читаемость в течение 1 мс, если вы не собираетесь использовать эти 1 мс.

Просто помните, что любой умный маленький взлом, который вы собрали, должен быть сохранен (и доказано, что он работает первым в этом отношении), где доступно столько стандартных / системных решений, что было доказано. (см. «Изобретая колесо»).

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

Answer 5

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

Answer 6

Я бы пошел с первым, используйте системный стек.При этом на языке FORTH существует два системных стека.Один - это стек возврата, а другой - стек параметров.Это предлагает хорошую гибкость.

Answer 7

Рекурсия может быть самым простым способом решения конкретной проблемы. Итеративное решение может потребовать больше кода и больше возможностей для ошибок. Стоимость тестирования и обслуживания может быть больше, чем выигрыш в производительности.

Answer 8

Хм, я думаю, это решает проблему ...

Размер стека, если я понял, не ограничивает вас тем или иным способом.

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

Избегайте рекурсии, когда можете. :)