Как проследить эту рекурсивную программу

Question

Мне было интересно, сможет ли кто-нибудь сказать мне, как эта программа достигает правильного ответа. Я попытался проследить его и не знаю, куда идти, потому что у него есть or, поэтому я смущен, как он должен быть прослежен. Спасибо за любые разъяснения.

Написать функцию раздела, который принимает список номеров xs, исходное положение i и желаемую сумму s и возвращает True или False в зависимости от того, возможно ли найти подпоследовательность элементов списка, начиная с позиции i которого сумма равна точно s. Заметим, что всегда можно создать подпоследовательность элементов, сумма которых равна точно 0, а именно пустая последовательность элементов.

def partition(xs,i,s): 
    print i,s 
    if i == len(xs): 
     return s == 0 
    else: 
     return partition(xs,i+1,s-xs[i]) or partition(xs,i+1,s) 

Answer 1

Модуль rcviz является хорошим инструментом, чтобы помочь визуализировать рекурсивные функции:

В края нумеруются порядком, в котором они были пройдены выполнением. 2. Края окрашены от черного до серого, чтобы указать порядок обхода: черные края сначала, серые края - последними.

Если следовать вызовы, которые пронумерованные 1-11 вы можете точно узнать, что происходит, i начинается в 0 затем переходит в 1, 2 3 и, наконец, 4, последнее значение на слева partitition([1,2,3,4],4,-2) поэтому он возвращает False для s == 0.

Далее мы идем туда, где i является 2 затем снова 3,4 и в конечном итоге с partitition([1,2,3,4],4,1) так s == 1 снова False.

Далее мы переходим от этапа 6, заканчивающегося partitition([1,2,3,4],4,5), где еще раз s == 0 является ложным.

Наконец в правом мы идем partitition([1,2,3,4],4,7) весь путь вниз к partitition([1,2,3,4],4,0) где s == 0 истинна и функция возвращает True.

Если вы берете первые четыре вызова, вы можете увидеть, как идет поток и как изменяется s.

partitition([1,2,3,4],1,7) # -> xs[i] = 1 s - 1 = 7 
partitition([1,2,3,4],2,5) # -> xs[i] = 2 s - 2 = 5 
partitition([1,2,3,4],2,5) # -> xs[i] = 3 s - 3 = 2 
partitition([1,2,3,4],2,5) # -> xs[i] = 4 s - 4 = -2 
s == 0 # -> False 

Answer 2

Возможно, эта версия, которая является логически эквивалентной, делает ее более понятной. Ключ в том, что return a or b эквивалентен if a: return a else: return b.

def partition(xs,i,s): 
print i,s 
if i == len(xs): 
    # Base case: If the goal is to sum to 0, we succeed. 
    return s == 0 
else: 
    # First, try including element i in our sum: 
    first_try = partition(xs,i+1,s-xs[i]) 
    if first_try: 
     return True 
    else: 
     # If first try failed, try not including element i 
     second_try = partition(xs,i+1,s) 
     return second_try 

Answer 3

Это объяснение того, как or работ в этом контексте:

return partition(xs,i+1,s-xs[i]) or partition(xs,i+1,s) 

возвратит partition(xs,i+1,s-xs[i]), если это выражение в True. If partition(xs,i+1,s-xs[i]) будет оценивать как False, partition(xs,i+1,s) будет возвращен (независимо от того, будет ли он оценен как True или False).

Примечание Вы можете проверить это с помощью следующего набора простых примеров:

In [1]: 1 or 2 # When both are True, the first is returned. 
Out[1]: 1 

In [2]: 0 or 2 # When the first is False, the second is returned. 
Out[2]: 2 

In [4]: 0 or False # When both are False, the second is returned. 
Out[4]: False 

Answer 4

Я думаю, что это становится намного легче понять, если это написано с лучшими именами и не индексирования:

def can_add_to(numbers, sumwanted): 
    if not numbers: 
     return sumwanted == 0 
    first, *rest = numbers 
    return can_add_to(rest, sumwanted-first) or can_add_to(rest, sumwanted) 

print(can_add_to([1, 4, 9, 25], 13)) 

Это то же самое, как у вас, только более читаемым. Тогда пояснение:

Если чисел нет, тогда ответ «да» тогда и только тогда, когда требуемая сумма равна нулю, и мы сразу можем сказать это.

В противном случае возьмите первое число (и остальное). Вы можете использовать его для суммы или нет.

С его помощью: can_add_to(rest, sumwanted-first) говорит вам, может ли оставшейся суммы (после вычитания first) производится из оставшихся чисел.

Неиспользование: can_add_to(rest, sumwanted-first) говорит вам, может ли сумма суммой быть произведена из оставшихся номеров.

Общий ответ «да» тогда и только тогда, когда вы можете сделать сумму с или безfirst. Вот почему вы берете два ответчика и or их вместе.