如果给定编程问题中的上述条件，并且我正在使用递归解决它，那么我是否违反了约束?这可能是因为递归也使用堆栈?对吗?
如果堆栈的深度(递归)是恒定的，并且不随输入的大小而变化，那么递归解可以是O(1)额外的空间。
一些编译器可能会做尾部调用优化(TCO)，如果递归调用是在函数的任何给定代码路径中执行的最后一条语句，则会删除递归调用。有了TCO，就没有调用堆栈相关的内存开销。
然而，请记住，O(1)约束可能会强制您选择特定的(可能是非递归的)算法，因此依赖尾部调用优化可能是不明智的，即使您知道您正在使用的编译器已经对您的代码进行了相关转换。至少，如果您依赖它，您应该明确地说出来，并通过参考语言规范、编译器文档和/或适当的反汇编来证明您对TCO的期望。
extra allowed space is O(1)
表示您的程序只能使用固定数量的空间，例如C。
根据big-O的定义，这意味着您的程序所需的空间不能取决于输入的大小，尽管C可以被设置得任意大。
因此，如果递归依赖于输入a(通常是这种情况)，则程序需要的空间不是O(1)。
进一步说明:
-
总是使用
1 Mb的程序占用O(1)空间。 -
一个总是使用
1 Tb的程序占用了O(1)空间b。 -
使用
N Mb的程序，其中N是输入的一部分，不使用O(1)空间，(它使用O(N)空间)。
长话短说，当你阅读O(1)时，只要在心里把它替换成常量。
。例如，foo(n) = foo(n - 1)，这里维护函数调用所需的堆栈空间为O(n) 。
b。当O符号上的材料评论忽略常量是如何麻烦时，这就是他们所说的。
如果递归的深度根据输入的大小而增长(通常是这样)，那么是的:您将使用无限大的堆栈内存。需求是用固定的内存量来解决这个问题。
关于告诉您必须使用的堆栈量为O(1)，并且无论输入大小如何都必须保持不变的其他答案，如果您希望以递归方式解决问题，它只留给您两种可能性:
- 固定深度递归，这意味着限制函数递归的时间。
- 尾部递归，这意味着对函数的递归调用必须是最后要计算的东西，从而触发TCO。(尾部调用优化)粗略地说，这意味着由于递归调用是函数执行中发生的最后一件事，而不是将调用上下文推入堆栈，现有的调用上下文将被新的调用上下文覆盖，有效地使用常量堆栈空间。
如果你使用递归来解决这个问题，那么你是在使用堆栈将数据传递到递归树。在这方面，您通常使用超过O(1)的空间。
我确实同意接受的答案，但我想指出的是，如果你使用的是带有尾部调用优化的语言(如clojure)，那么你可以使用O(1)空间来解决问题，这将使用没有此功能的语言(如java)使用更多空间。
存储复杂度为0(1)意味着你的算法必须使用恒定的存储量。也就是说，它必须在包含10个元素的集合上使用与1000个元素相同的存储空间。
您可能应该使用迭代来完成此操作。