在使用 Java（或任何其他程序语言）进行编程时，我经常在递归解决问题和迭代解决问题之间进行选择。递归选项通常比迭代解决方案更优雅，所以我通常选择递归解决方案。除了一个例外：
担心堆栈溢出如果最大堆栈深度与输入的大小成线性比例（或更糟），我倾向于避免递归解决方案。然而，我意识到在许多其他语言中（甚至是针对 JVM 的语言，例如 Scala 和 Clojure），许多算法（例如基本列表算法）通常以递归方式表示，其中最大堆栈深度与列表的长度成正比。(1)那么，我对线性堆栈深度算法中堆栈溢出的担忧是否合理？
TL;DR：什么“堆栈深度复杂度”被认为是合理的？对数复杂度，例如递归二分搜索，O(log N)肯定没问题，但是O(N)，O(N log N)，O(N 2 )怎么样？你通常会在哪里画线？(2)
(1) 我意识到这些语言有时支持 @tailrec 之类的东西，但这个问题涉及 Java、C# 等。
(2) 请注意，我不关心 CPU 开销等。只是堆栈深度。
堆栈深度复杂性是要考虑的一件事，但另一件事是输入大小本身。
如果问题排除了其领域的大输入（在开发过程中很长一段时间），那么我们可以使用递归解决方案（当然，递归解决方案不能超过最大可能输入堆栈的容量）。
如果未定义输入大小，则 O(1) 堆栈深度或 O(log N) 堆栈深度是可以接受的，恕我直言。如果输入大小的实际上限大到超过堆栈容量，则 O(log N) 可能是不可接受的。但是，我认为这种情况很少见。
如果不问自己希望能够支持什么尺寸的输入，就无法回答这个问题。
如果您正在处理一副扑克牌，堆栈上的线性空间复杂度绝对没问题，如果您正在处理巨大的文本文件，则可能完全没有希望。您需要计算出您的应用程序的最大输入大小，或者更确切地说，您不介意它失败的最大输入。
我们一直这样做。例如，每次在 Java 中声明一个数组时，您都知道该数组中的元素不能超过 2 31个。这有关系吗？这是否意味着程序已损坏？可能不是; 但有时确实如此，如果您希望能够处理大量输入。
因此，我认为您不能对此过于规范。如果有人问（笼统地说）什么时间复杂度合适，你会怎么说？你可能会说一些一般原则：通常线性是可以的，通常指数是不好的......但真正的答案是，这取决于你在做什么。