如果给出了编程问题中的上述条件，并且我正在使用递归解决它，那么我是否违反了约束条件？可能是因为递归也用栈？对吗？
最佳答案
如果栈的深度(递归)是恒定的，并且不会随着输入的大小而改变，那么递归解决方案可以是 O(1) 额外空间。
一些编译器可能会执行尾调用优化 (TCO) 并删除递归调用，如果它们是通过函数在任何给定代码路径中执行的最后一条语句。使用 TCO，没有与调用堆栈相关的内存开销。
但是，请记住，O(1) 约束可能会强制您选择特定的(可能是非递归的)算法，因此即使您了解编译器，依赖尾调用优化也可能是不明智的正在使用对您的代码进行了相关改造。至少，如果您依赖它，您应该明确说明，并通过引用语言规范、编译器文档和/或适当的反汇编来证明您对 TCO 将发生的期望是合理的。
关于algorithm - 规定extra allowed space是O(1)是什么意思？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24360546/