Рекурсивная функция, возвращающая None без веской причины

Question

Моя цель - написать функцию, которая принимает список целых чисел - ints - и сумму сумм - s - и возвращает список первых двух целых чисел в списке, которые в сумме составляют s в порядке их появления в списке слева направо. У меня есть функция print на консоль для каждой итерации, и все выглядит хорошо, за исключением того, что она всегда возвращает None, и я понятия не имею, как. Мой код:

def sum_pairs(ints, s, a=0, b=1):
    if a == len(ints)-1 or b > 666:
        return None
    if b < len(ints):
        print(s, a,b,[ints[a],ints[b]], ints[a] + ints[b])
        if ints[a] + ints[b] == s:
            x = ints[a]
            y = ints[b]
            print([x,y], type([x,y]), [x,y] is None)
            return [x, y]
        else: 
            sum_pairs(ints, s, a, b=b+1)
    else:
        sum_pairs(ints, s, a=a+1, b=a+2)

Я даже проверил, является ли [x,y] значением None на шаге перед оператором возврата, и он всегда возвращает False, но каким-то образом функция все еще возвращает None. Может кто-нибудь заполнить меня? Я новичок в рекурсии, так что, возможно, проблема в этом.

Answer 1

Я бы начал писать обобщенную функцию c combinations, которая генерирует комбинации указанного размера -

def combinations(items, size):
  if size == 0:
    yield ()
  elif not items:
    return
  else:
    head, *tail = items
    for p in combinations(tail, size - 1):
      yield (head, *p)
    yield from combinations(tail, size)

Мы полагаемся на генераторы Python, которые лениво произвести вывод. Мы можем использовать list для получения всех результатов -

data = [ 1, 2, 3, 4, 5, 6, 7, 8 ]

list(combinations(data, 2))
# [ (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 3),
#   (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6),
#   (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7),
#   (5, 8), (6, 7), (6, 8), (7, 8) ]

. Он может легко генерировать комбинации других размеров, и итеративный ввод может содержать элементы любого типа -

list(combinations("abcd", 3)))
# [ ('a', 'b', 'c'), ('a', 'b', 'd'),
#   ('a', 'c', 'd'), ('b', 'c', 'd') ]

* 1013. * Написав combinations как отдельную функцию, мы распутываем проблемы нашей программы. В результате sum_pairs легко написать и протестировать. Мы передаем 2 в качестве аргумента size, потому что мы хотим генерировать пары (из двух чисел) -

def sum_pairs(ints, goal):
  for p in combinations(ints, 2): # <-- use combinations
    if sum(p) == goal:
      return p
  return None                     # <-- don't forget unsolvable case


print(sum_pairs(data, 13))
# (5, 8)

Поскольку мы используем генераторы Python, sum_pairs вернется сразу после нахождения ответа. Такое поведение при коротком замыкании означает, что ненужные комбинации или итерации не будут потрачены впустую.

Если задана недостижимая цель, sum_pairs вернет None -

print(sum_pairs(data, 99))
# None

---

Небольшая модификация демонстрирует эффективность нашего combinations generi c. В этой программе any_sum найдет комбинацию любого размера, которая соответствует нашей ожидаемой цели -

def any_sum(ints, goal):
  for size in range(len(ints)):
    for p in combinations(ints, size + 1):
      if sum(p) == goal:
        return p
  return None

Хотя это не самая эффективная реализация any_sum, она действительно показывает, как combinations может быть повторно использован без введения новой сложности -

print(any_sum(data, 17))
# (2, 7, 8)

print(any_sum(data, 25))
# (4, 6, 7, 8)

print(any_sum(data, 33))
# (3, 4, 5, 6, 7, 8)

print(any_sum(data, 99))
# None