Confusion about python recursion

Asked by At

I was writing a recursive function to solve a problem where essentially you are trying to find all combinations to reach the target sum with a given number of number and each number is smaller than a certain limit.

The code I wrote looks like:

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")

but this gives the wrong answer.

If I change one line and makes it:

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")

Then everything is correct. I am really confused about why this is the case. I tried to do some debugging and found that append and pop were not working the way I expected them to do. It would be great if anyone can explain what exactly is the difference between the two ways I did the function.

1 Answers

1
cdlane On Best Solutions

The first program adds an item to the end of res, makes a recursive call to findSchedulesHelper() and after the call, removes the item added:

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

Whereas the second program passes a new list that is everything in res plus the extra item. It doesn't need to clean up after the recursive call:

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

One difference between the two is due to this code:

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

That is, the recursive call to findSchedulesHelper() has the potential to change res. If it does, the res.pop() on return may be removing something else than you think it is. And there may be extra data at the end of res on the next call. The second program doesn't suffer this issue as it passes a copy of res and never again looks at, or reuses, the copy.

The next potential problems are the multiple calls to:

results.append(res)

In the first program, you're passing the same res list, so results ends up with multiple pointers to res all of which are the same exact list, always reflecting its current state, not its state when it was added to results. In the second program, you're passing a copy of res so all the entries on results are different, the state of res when it was added to results.