严格来讲面试时要求空间复杂度O(1)的题目是否能用递归

最近面试时遇到了一到链表题，有了一些关于空间复杂度疑问。
递归时是要在内存里形成一个function call stack的，占用空间和递归树一样大小，这部分是不是计入空间复杂度之内呢？

stack有两种，自己设置的stack，用linkedList实现。还有就是系统自带的递归stack，都是要计入空间复杂度的，而且你要注意，系统自带的stack是有上限的，我记得很多oj的上限是100-200之间，如果你是用DFS这种算法，很容易就会看到stackOverflow。所以一定要小心的使用递归，如果可以最好少用。

感觉是这样的.. 如果是说空间复杂度只能是o1 的话, 说明是非o(n)的结构...

链表o1 应该是说可以多造一个头., 至于你说用recursion的方法, 应该是极其不建议的. 因为你不知道这个链表有多长, 比如反向打印时用recursion就不会是o 1 空间了.. 但是你先转向了再打印就可以

我感觉