Analyzing Space Complexity of Recursive Function

In our CS course, we haven't covered how to analyse space complexity. We have though, been given the task of implementing an $\Theta(n)-time$ algorithm for reversing a singly linked list, with a maximum $O(1)-space$ (besides the actual array).

This is my implementation in Python:

#x0.next = x1
def invert(x0,x1):
    next = x1.next
    x1.next = x0
    if next is None:
        return x1
    else:
        invert(x1,next)

def invertSLinkyList(head):
    firstNext = head.next
    head.next = None
    x = 0
    x = invert(head,firstNext)
    return x

To give a quick verbal description: Essentially, we iterate through each node (x0) and set its next (x1) to the previous node. We then call this recursively on the original next (x1) on its next (x1.next), until we reach the end node (which has next = None) at which case we return this node as the new head.

I have analysed its time complexity to be $\Theta(n)$ based on:

Each call creates 1 child note at a constant time
We create n children as the code iterates through the whole list.
It takes $O(1)$ to "merge"

My question is then; How do I go about analysing its space complexity?

OBS: Please not that this is not a graded assignment. It is a part of my weekly training exercises.

Solution

To analyze space complexity, you are analyzing whether the amount of memory is dependent on n. In other words, as your algorithm input size changes, number of nodes for the LL in this case, does that affect the space used?

In this case, by using recursion, you are adding frames to the call stack and using memory that way. Since you mention that you make a recursive call per node, can you reason the space complexity? How does that relate to your entries?

In this case, you won't return until next is none, at that point how many stack frames would be added to the call stack?

In this case, n frames would be put on the call stack, therefore you would get a Space complexity of O(n)