Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?

Question

Given this naive recursive function:

def largest_tower(heights_and_widths, prev_height=1000, prev_width=1000):
    if not heights_and_widths:
        return 0

    results = {0}

    for i in range(len(heights_and_widths)):
        current_height, current_width = heights_and_widths[i]

        if current_height < prev_height and current_width < prev_width:
            subarray = heights_and_widths[:i] + heights_and_widths[i+1:]
            results.add(1 + largest_tower(subarray, current_height, current_width))

    return max(results)

At first sight, I would have said that the time complexity of this function is O(n^2). But, if I'm not wrong, explained in plain words would be: This function may call itself (n-1) + (n-2) + ... + 1 times, being that O(n^2), but a total of n times, so the actual time complexity is O(n^3). Am I right?

And for the memoized version:

def largest_tower_memoized(heights_and_widths, prev_height=1000, prev_width=1000, cache=None):
    if not heights_and_widths:
        return 0

    if cache is None:
        cache = {}

    results = {0}

    for i in range(len(heights_and_widths)):
        current_height, current_width = heights_and_widths[i]

        if current_height < prev_height and current_width < prev_width:
            subarray = tuple(heights_and_widths[:i] + heights_and_widths[i+1:])

            if (current_height, current_width) not in cache:
                cache[(current_height, current_width)] = largest_tower_memoized(
                    subarray, current_height, current_width, cache
                )
            results.add(1 + cache[(current_height, current_width)])

    return max(results)

I find this more complicated to explain. My intuition tells me that it's O(n), since we the recursion tree for each input is generated only once, but I'm not sure.