递归反转单链表时占用内存栈空间，为何空间复杂度被标注为O(1)

你给出的这段递归反转单链表的实现，按照通用的算法复杂度计算规范，空间复杂度应为O(n)，部分资料标注为O(1)通常是以下几种原因：

• 第一种是资料本身有误，混淆了递归实现和迭代实现的复杂度。双/三指针的迭代反转方案不需要额外的栈空间，仅用几个临时变量就能完成操作，空间复杂度才是O(1)，很多资料内容搬运时没有区分两种实现，直接套错了复杂度。
• 第二种是复杂度统计口径的问题，部分资料计算额外空间时，仅统计开发者手动显式申请的堆内存，不统计程序运行时隐式占用的调用栈空间。你这段代码确实没有申请额外的节点、数组等堆内存，所有修改都在原链表的空间上完成，如果按照这个不严谨的统计规则，就会被标注为O(1)。但这种计算方式没有参考价值，实际运行时如果链表长度过长，递归深度过大会直接触发栈溢出，本质就是调用栈占用的O(n)空间导致的。
• 第三种是混淆了普通递归和可尾递归优化的实现。你给出的这段代码不属于尾递归：递归调用返回后还需要执行head.next.next=head、head.next=None的操作，哪怕是支持尾递归优化的语言也没法优化这段代码的栈空间。只有改写成尾递归形式的反转实现，在开启尾递归优化的环境下，空间复杂度才会被优化到O(1)，部分资料会把这个优化后的结果直接套用到所有递归实现上，导致标注错误。

你给出的递归实现代码如下：

def reverse(self,head):
        if(head==None or head.next==None):
            return head
        res=self.reverse(head.next)
        head.next.next=head
        head.next=None
        return res

内容的提问来源于stack exchange，提问作者Satwik varma