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

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

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

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

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