Q:

Time Space Complexity of Recursive Functions

This is from a leetcode problem here: https://leetcode.com/problems/reverse-string/solution/
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Solution 1:
class Solution:
    def reverseString(self, s):
        def helper(left, right):
            if left < right:
                s[left], s[right] = s[right], s[left]
                helper(left + 1, right - 1)

        helper(0, len(s) - 1)

Time complexity : O(N) time to perform N/2 swaps.
Space complexity : O(N) to keep the recursion stack.
Solution2:
class Solution:
    def reverseString(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left, right = left + 1, right - 1

Time complexity: O(N) to swap N/2 element.
Space complexity: O(1), it's a constant space solution.
Can someone please explain why the space complexity in solution 2 is O(1) while the space complexity in solution 1 is O(n)?
Is it because solution 1 requires a function call? 
Thanks in advance!

A:

When you call a function recursively, behind the scenes a new stack frame is created to hold the return address and variables you create in the new call.
Each recursive call does this, so if a function calls itself n/2 times, that's O(n) storage space.

