Путаница с рекурсией Python

Question

Я писал рекурсивную функцию для решения проблемы, когда по сути вы пытаетесь найти все комбинации для достижения целевой суммы с заданным числом чисел, и каждое число меньше определенного предела.

Код, который я написал, выглядит следующим образом:

results = []

def findSchedulesHelper(workHours_left, dayHoursLimit, days_left, res):
    if workHours_left < 0:
        return
    elif workHours_left > 0 and days_left == 0:
        return
    elif workHours_left == 0 and days_left != 0:
        for i in range(days_left):
            res.append(0)
        results.append(res)
        return
    elif days_left == 0 and workHours_left == 0:
        results.append(res)
        return
    else:
        for i in range(dayHoursLimit + 1):
            res.append(i)
            findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res)
            res.pop()


def findSchedules(workHours, dayHours, pattern):
    # Write your code here
    num_question_mark = 0
    total_hours_so_far = 0
    for char in pattern:
        if char == "?":
            num_question_mark += 1
        else:
            total_hours_so_far += int(char)

    hours_left_to_fill = workHours - total_hours_so_far

    for i in range(dayHours + 1):
        findSchedulesHelper(hours_left_to_fill - i, dayHours, num_question_mark - 1, [i])
    print results

findSchedules(3,2,"??2??00")

, но это дает неправильный ответ.

Если я изменю одну строку и сделаю это:

results = []

def findSchedulesHelper(workHours_left, dayHoursLimit, days_left, res):
    if workHours_left < 0:
        return
    elif workHours_left > 0 and days_left == 0:
        return
    elif workHours_left == 0 and days_left != 0:
        for i in range(days_left):
            res.append(0)
        results.append(res)
        return
    elif days_left == 0 and workHours_left == 0:
        results.append(res)
        return
    else:
        for i in range(dayHoursLimit + 1):
            findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res + [i])


def findSchedules(workHours, dayHours, pattern):
    # Write your code here
    num_question_mark = 0
    total_hours_so_far = 0
    for char in pattern:
        if char == "?":
            num_question_mark += 1
        else:
            total_hours_so_far += int(char)

    hours_left_to_fill = workHours - total_hours_so_far

    for i in range(dayHours + 1):
        findSchedulesHelper(hours_left_to_fill - i, dayHours, num_question_mark - 1, [i])
    print results

findSchedules(3,2,"??2??00")

Тогда все будет правильно.Я действительно не понимаю, почему это так.Я попытался выполнить некоторую отладку и обнаружил, что append и pop работают не так, как я ожидал.Было бы здорово, если бы кто-нибудь мог объяснить, в чем именно разница между двумя способами, которыми я выполнял функцию.

Answer 1

Первая программа добавляет элемент в конец res, делает рекурсивный вызов findSchedulesHelper() и после вызова удаляет добавленный элемент:

res.append(i)
findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res)
res.pop()

В то время как вторая программа передает новый список, который содержит все в res плюс дополнительный элемент. Не нужно убирать после рекурсивного вызова:

findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res + [i])

Одно из различий между ними связано с этим кодом:

for i in range(days_left):
    res.append(0)

То есть рекурсивный вызов findSchedulesHelper() может измениться res. Если это произойдет, res.pop() при возврате может удалить что-то еще, чем вы думаете. И может быть дополнительные данные в конце res при следующем вызове. Вторая программа не сталкивается с этой проблемой, поскольку передает копию res и никогда больше не просматривает и не использует повторно копию.

Следующие потенциальные проблемы - это множественные вызовы:

results.append(res)

В первой программе вы передаете один и тот же список res, поэтому results заканчивается несколькими указателями на res, каждый из которых является тем же точным списком, всегда отражая его текущее состояние, а не его состояние, когда оно было добавлено к results. Во второй программе вы передаете копию res, поэтому все записи в results отличаются , состояние res, когда он был добавлен в results.