如果给出了编程问题中的上述条件，而我正在使用递归来解决它，那我是否违反了约束？可能是因为递归还使用堆栈吗？这样对吗？
最佳答案
如果堆栈的深度(递归)是恒定的，并且相对于输入大小不变，则递归解决方案可以是O(1)额外的空间。
如果某些编译器是通过函数在任何给定代码路径中执行的最后一条语句，则它们可能会进行尾部调用优化(TCO)并删除递归调用。使用TCO，不存在与调用堆栈相关的内存开销。
但是，请记住，可能会强加O(1)约束来强制您选择特定的(可能是非递归的)算法，因此即使您知道所使用的编译器具有尾部调用优化，也可能是不明智的对您的代码进行了相关的转换。至少，如果您依靠它，则应该明确地说出并期望通过引用语言规范，编译器文档和/或适当地反汇编来期望获得TCO。