Рекурсия для создания подмножеств списка

Question

Я хотел бы знать для этой функции, почему после выполнения и возвращает [[], [1]], которая является последней строкой функции? Затем он будет запускать строку меньше = genSubset (L [: - 1]) снова и снова. Я визуализировал код из pythontutor. Однако я не понимаю, почему это так работает. Кто-нибудь, пожалуйста, просветите меня. Спасибо.

Эта функция генерирует все возможные подмножества данного списка, например, входным списком является [1,2,3]. Он вернет [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] ».

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]] #list of empty list
    smaller = genSubsets(L[:-1]) # all subsets without last element
    extra = L[-1:] # create a list of just last element
    new = []
    for small in smaller:
        new.append(small+extra)  # for all smaller solutions, add one with last element
    return smaller+new  # combine those with last element and those without

print(genSubsets([1,2,3]))

Answer 1

Эта функция рекурсивна , то есть вызывает сама себя. когда он завершает одну итерацию рекурсии - возвращается туда, где остановился. Это точно в строке smaller = getSubsets(L[:-1]), но обратите внимание, что он не будет запускать его снова , а вместо этого продолжит, пока не закончит вызов. Эта рекурсия происходит n раз (где n - длина списка), и вы увидите такое поведение ровно n раз, прежде чем функция наконец вернет подмножества.

Надеюсь, я правильно понял вопрос и смог ответить на него: )