# Confusion about python recursion

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.

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`.