Понятие «локальная» переменная рекурсии в Python

Question

Я просто узнаю о рекурсии и пытаюсь применить ее в некоторых целях для удовольствия, прийти к пониманию. (Да, все это дело лучше сделать три вложенные для петель)

def generate_string(current_string, still_to_place): 
    if still_to_place: 
     potential_items = still_to_place.pop(0) 
     for item in potential_items: 
      generate_string(current_string + item, still_to_place) 
      #print("Want to call generate_string({}, {})".format(current_string + item, still_to_place)) 
    else: 
     print(current_string) 
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']]) 

Если я закомментируйте рекурсивный вызов и раскомментируйте печати, он печатает именно то, что я надеюсь, что он будет звонить. Однако просто раскомментирование печати показывает, что он вызывает пустой массив still_to_place, даже если он все еще должен иметь [d, e, f], [g, h, i] из рекурсии «выше».

Что мне недостает в моем понимании? Благодаря!

Answer 1

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

#1st time 
current_string = "" 
still_to_place = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']] 

Мы начинаем пропускание в приведенных выше данных, однако, как мы пройти через то, что происходит, мы первый поп первого массива ['a', 'b', 'c'], и мы начинаем перебирать этот Popped массива. Однако, так как мы назвали .pop (0), теперь мы только последнюю часть массива, still_to_place.pop(0) на первом рекурсивного вызова, который сделал для generate_string()

#2nd time 
current_string = "a" 
still_to_place = [['d', 'e', 'f'], ['g', 'h', 'i']] 

Это именно то, что было в current_string и still_to_place при первом вызове рекурсивного вызова. Теперь мы начнем выполнение функции с самого начала. Мы снова вызываем функцию pop, удаляя второй массив ['d', 'e', 'f']. Теперь мы остаемся только с третьим и последним массивом.

#3rd time 
current_string = "ad" 
still_to_place = [['g', 'h', 'i']] 

Как мы перебираем ['g', 'h', 'i'], потому что still_to_place теперь пуст. (Мы только что вытащили последний массив.) Любые вызовы generate_string перейдут непосредственно к предложению else, и мы собираемся распечатать строку «объявление» плюс значения в массиве, который мы только что выскочили.

#4th, 5th and 6th time 
still_to_place = [] 
current_string = "adg" 

still_to_place = [] 
current_string = "adh" 

still_to_place = [] 
current_string = "adi" 

Теперь мы продолжим, когда последний рекурсивный вызов прекратился, когда мы проходим второй раз. Здесь все запутывается. Когда мы остановились current_string = "a" и still_to_place было изначально [['d', 'e', 'f'], ['g', 'h', 'i']], но с тех пор мы вытащили все из массива. Видите ли, массивы ведут себя иначе, чем числа или строки. Все версии массива используют одни и те же данные. Вы меняете данные один раз, он меняет его везде, где используется массив. (объекты и словари также ведут себя таким образом.)

Итак, все, что сказал still_to_place = [], и still_to_place останутся пустыми для остальной части рекурсивных вызовов. Потенциальные_итуты все еще имеют данные, которые он вытащил из ['d', 'e', 'f']. Мы уже выполнили «d» строка с шагом # 4, # 5 и # 6, так что мы можем закончить, где мы из

#7th and 8th times 
still_to_place = [] 
current_string = "ae" 

still_to_place = [] 
current_string = "af" 

Еще раз potential_items имеет ['a', 'b', 'c'] и мы уже выполнили «а ». В отличие от still_to_place, потенциальные_имяты - это локальная переменная с меньшей областью. Если вы знаете, как работают области действия, то это будет сделано, потому что мы можем иметь несколько потенциальных_итем, но это то же самое, что и для_пользователя. Каждый раз, когда мы выталкивали элемент still_to_place, мы добавляли всплывающий результат к новой переменной потенциальных элементов с ограниченной областью. still_to_place был глобальным для всей программы, поэтому одно изменение на still_to_place приведет к изменениям, которые не ожидаются.

Надеюсь, я сделал вещи более запутанными и не менее запутанными. Оставьте комментарий о том, что вам нужно больше разъяснений.

Answer 2

Правильно, это ожидаемое поведение. Причина в том, что still_to_place разделяется между вызовами каждой функции. Объекты Mutable в Python «передаются по назначению», что означает, что если вы передаете список функции, эта функция разделяет ссылку на список SAME. This thread has more detail.

Таким образом, каждый раз, когда вы вызываете still_to_place.pop (0), вы выбираете список во всех рекурсивных вызовах. Все они имеют один и тот же список.

Такое поведение не всегда желательно, часто вы хотите, чтобы ваш список был неизменным. В этом случае вам необходимо передать рекурсивный вызов модифицированную копию структуры данных. Вот что ваш код будет выглядеть, используя неизменный подход:

def generate_string(current_string, still_to_place): 
    if still_to_place: 
     potential_items = still_to_place[0] 
     for item in potential_items: 
      generate_string(current_string + item, still_to_place[1:]) 
      print("Want to call generate_string({}, {})".format(current_string + item, still_to_place)) 
    else: 
     print(current_string) 
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']]) 

Как правило, методы на объекте (например, .pop) доработаем его на месте. Кроме того, разные языки подходят к изменчивости по-разному, на каком-то языке структуры данных ВСЕГДА неизменяемы.