Рекурсивная функция не возвращает созданную строку

Question

Я новичок в Python, так что, возможно, это может быть глупый вопрос.

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

def knapsackRecursive(items, maxNum, bestResponse): 
    print('items=' + str(items) + ', maxNum=' + str(maxNum)) 
    referenceIndex = 0 
    editableMaxNum = maxNum 
    if editableMaxNum == 0: 
     bestResponse = '0' 
    else: 
     for i in reversed(items): 
      item = int(i) 
      if editableMaxNum >= item: 
       if referenceIndex == 0: 
        referenceIndex = items.index(str(item)) 
       editableMaxNum -= item 
       bestResponse = '1' + bestResponse 
      else: 
       bestResponse = '0' + bestResponse 
     if editableMaxNum != 0: 
      bestResponse = '' 
      if referenceIndex != 0: 
       for k in range(0, len(items) - referenceIndex): 
        bestResponse = '0' + bestResponse 

       knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) 
      else: 
       bestResponse = '0' 

    print('bestResponse=' + str(bestResponse)) 
    return bestResponse 

Items являются константами, которые являются [ '1', '2', '4', '10', '20', '40', '63', '105']. Также начальная bestResponse - пустая строка.

, если я изложу maxNum, как 41, выход:

items=['1', '2', '4', '10', '20', '40', '63', '105'], maxNum=41 
bestResponse=10000100 

Но если я устанавливаю maxNum, как 71, выход:

items=['1', '2', '4', '10', '20', '40', '63', '105'], maxNum=71 
items=['1', '2', '4', '10', '20', '40'], maxNum=71 
bestResponse=10011100 
bestResponse=00 

Почему bestResponse выход печатается дважды для ввода 71? И хотя первая печать правильная, почему функция возвращает второй результат, который является неправильным?

EDIT

Я изменил knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) в return knapsackRecursive(items[:referenceIndex], maxNum, bestResponse). Кажется, это разрешено. Очевидно, я допустил ошибку при использовании рекурсивного. Но все же я не мог понять, почему функция возвращает результат первого вызова вместо второго вызова, который, как ожидается, генерирует правильный ответ.

Answer 1

Я думаю, что вы должны сделать:

best_response = knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) 

вместо

knapsackRecursive(items[:referenceIndex], maxNum, bestResponse)