Хорошо иметь глубину стека, линейно пропорциональную некоторому размеру ввода?

При программировании на Java (или на любом другом языке процедур, если на то пошло), я часто выбираю решая что-то рекурсивно vs итеративно. Рекурсивный вариант часто более элегантный, чем итеративное решение, поэтому я обычно использую рекурсивное решение. За одним исключением:

Беспокойство о переполнении стека. Я стараюсь избегать рекурсивных решений, если максимальная глубина стека линейно пропорциональна размеру ввода (или хуже). Однако я понимаю, что во многих других языках (даже для таргетинга на JVM, таких как Scala и Clojure) многие алгоритмы, такие как, например, алгоритмы базового списка, часто выражаются рекурсивно, где максимальная глубина стека пропорциональна длине список. ⁽¹⁾ Итак, мои заботы о переполнении стека в алгоритмах с линейной стекой-глубиной оправданы?

TL; DR: Какая "сложность глубины стека" считается разумной? Логарифмическая сложность, рекурсивный двоичный поиск, например, O (log N), конечно, хорошо, но как насчет O (N), O (N log N), O (N ²)? Где вы обычно рисуете линию? ⁽²⁾

^{(1) Я понимаю, что такие языки иногда поддерживают такие вещи, как @tailrec, но этот вопрос касается Java, С# и т.д.}
^{(2) Обратите внимание, что я не обеспокоен загрузкой процессора и т.д. Просто глубина стека.}

Ответ 1

Вы не можете ответить на этот вопрос, не спрашивая себя, какой размер ввода вы хотите поддерживать.

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

Мы делаем это все время. Например, каждый раз, когда вы объявляете массив в Java, вы знаете, что массив не может содержать в нем не более 2 элементов ³¹. Это имеет значение? Означает ли это, что программа нарушена? Возможно нет; но иногда это происходит, если огромный вход - это то, с чем вы хотите иметь дело.

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

Ответ 2

Сложность глубины стека - это одна вещь, которую нужно учитывать, но еще одна вещь - сам размер ввода.

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

Если размер ввода не определен, допустима глубина стека O (1) или глубина стека O (log N), IMHO. Возможно, что O (log N) может быть неприемлемым, если практический верхний предел размера ввода астрономически большой, что превышает емкость стека. Однако, я думаю, что такой случай будет довольно редок.