Рекурсия — почему этот код для печати последовательности чисел не работает
Я прошу прощения за то, что задаю здесь такой тривиальный вопрос для новичков, но каждый раз, когда я делаю два шага вперед в понимании рекурсии, я, кажется, делаю три шага назад. Я не могу понять, почему этот простой код для хранения n чисел в массиве дает пробелы. Я могу заставить его работать, выполнив закомментированную часть, но в верхней части, которая не работает, я предположил, что y и x будут заполнены, когда кадр стека раскручивается, и массив должен возвращать список чисел. Может кто-нибудь объяснить, что не так с моим предположением и как визуализировать рекурсию и как использовать результаты, когда вызовы выполняются рекурсивно и когда возвращаемые значения распространяются обратно в основную функцию?
def nums(n,x):
if n == 0:
return n
else:
y=(nums(n-1,x))
x.append(y)
return x # output was all blanks
# nums(n-1,x)
# x.append(n)
return x # This works
x=[]
print(nums(7,x))
Ответы 1
Способ, которым мы обычно учим это с помощью рекурсии, состоит в том, чтобы делать трассировки стека с разными значениями, чтобы продемонстрировать поток.
nums(0, []) => 0 # n.b., this is a scalar, not an array based on the code above
nums(1, []) =>
y = (nums(0, x)) => 0 (from above) # n.b., this might be interpreted as a tuple since we have surrounded it with parentheses, best to avoid enclosing parentheses if you don't need them
x.append(y) => x = [ 0 ]
return x => [ 0 ]
Теперь мы усложняем задачу, потому что x — это list, поэтому возвращается передается по ссылке. Таким образом, для n > 1 мы будем добавлять x к самому себе, что и вызовет проблему.
nums(2, []) =>
y = nums(1, []) =>
y = nums(0, []) =>
y = 0
x = [ 0 ]
=> [ 0 ]
x.append(x = [ 0 ]) => yields a circular reference since we are appending x to itself
Возможно, вы намеревались использовать семантику очистки стека, но если это было намерением, нам нужны свежие списки в качестве локальных переменных, поскольку мы делаем рекурсию:
def nums(n):
if n == 0:
return [ 0 ]
return [ n ] + nums(n - 1)
Вы, кажется, не приняли ни одного ответа ни на один из ваших предыдущих вопросов. Возможно, просмотрите эти старые вопросы и примите ответ, который решил вашу проблему; или, если хотите, опубликуйте свой собственный ответ и примите его. Принятие ответа поможет будущим посетителям отметить вопрос как решенный. См. также помощь. Низкий уровень принятия, вероятно, отпугнет пользователей от того, чтобы тратить свое время на чтение ваших вопросов.