Вопрос с вопросом о стеке

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

Если вам нужна какая-то пользовательская функциональность, которая недоступна в системе, затем перейдите к опции 2, используйте опцию 1. Зачем изобретать колесо?

Answer 5

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

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

Answer 9

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