Количество итераций в рекурсивной функции
Я пишу рекурсивную функцию для перестановки цифр от 0 до n. Программа вернет полученную перестановку th. Все это работает хорошо, но мне пришлось использовать дешевый прием определения count как списка, то есть count=[0]. Таким образом, я использую свойства списков, чтобы правильно обновлять переменную count[0] на каждой итерации.
В идеале я хотел бы вместо этого определить count как целое число. Однако это не работает, потому что count обновляется только локально, в рамках функции в момент ее вызова.
Каков правильный способ подсчета итераций в такой рекурсивной функции?
Ниже я показываю код. Это работает, но я ненавижу то, как я использую здесь count.
import numpy as np
N=10
available=np.ones(N)
def permutations(array, count=[0], n=N, start=0, end=N, th=100):
if count[0]<th:
for i in range(n):
if available[i]:
array[start]=i
if end-start>1:
available[i]=0
permutations(array, count, n, start+1, end)
available[i]=1
else:
count[0]+=1
break
if count[0]==th:
a=''.join(str(i) for i in array)
return a
def main():
array=[0 for _ in range(N)]
count=[0]
print(permutations(array, count, N, start=0, end=N))
if __name__= = "__main__":
main()
Что-то очень подозрительное в вашем коде: когда вы делаете рекурсивный вызов permutations(array, count, n, start+1, end), вы полностью игнорируете возвращаемое значение.
В общем, я бы рекомендовал любой ценой избегать глобальных переменных для такой функции. Почти наверняка существует лучший способ. Обратите внимание, что ваша переменная available также является глобальной переменной. Этого, наверное, тоже можно избежать.
Ответы 2
Не обязательно идеально, но для ответа на вопрос можно использовать глобальную переменную следующим образом:
import numpy as np
N = 10
available = np.ones(N)
count = 0
def permutations(array, n=N, start=0, end=N, th=100):
global count
if count < th:
for i in range(n):
if available[i]:
array[start] = i
if end-start > 1:
available[i] = 0
permutations(array, n, start+1, end)
available[i] = 1
else:
count += 1
break
if count == th:
return ''.join(str(i) for i in array)
def main():
array = [0 for _ in range(N)]
print(permutations(array, N, start=0, end=N))
print(f'{count=}')
if __name__ == "__main__":
main()
Выход:
0123495786
count=100
Спасибо, моя ошибка заключалась в том, что я написал global count вне области действия функции, поэтому я получил ошибку local variable 'count' referenced before assignment.
Различные способы обновления переменной из других областей... и каждый со своими преимуществами и недостатками (производительность, доступ к переменной,...): с глобальным подходом (как это сделал Пингу), с неместным и с атрибутом функции.
Рассматриваемый пример, функция факториала, является просто иллюстративным, но его можно легко адаптировать к вашему случаю.
def fact_global(n):
global counter
counter += 1
if n == 1:
return 1
return n*fact_global(n-1)
def fact_nonlocal(n):
counter = 0
def __fact(n):
nonlocal counter
counter += 1
if n == 1:
return 1
return n*__fact(n-1)
return __fact(n)
def fact_attr(n):
fact_attr.counter = 0
def __fact(n):
fact_attr.counter += 1
if n == 1:
return 1
return n*__fact(n-1)
return __fact(n)
n = 10
# case: global
counter = 0
fact_global(n)
print('global', counter)
# case: nonlocal
fact_nonlocal(n)
import inspect
fr = inspect.currentframe()
print('nonlocal', fr.f_locals['counter']) # not recommended, just for curiosity!
# case: function's attribute
fact_attr(n)
print('attr', fact_attr.counter)
Получение значения исследуемой переменной довольно просто с global-настройкой и атрибутом функции, но не тривиально (и не рекомендуется) с nonlocal (проверка — это скорее инструмент отладки).
Вот частичный результат верстака:
n=860
fact_nonlocal(n): 2.60644 ± 0.00586
fact_global(n): 2.74698 ± 0.02283
fact_attr(n): 3.01219 ± 0.00539
Результаты имеют тот же порядок (из-за ограничений хоста тестировалось только с максимальным значением n=860, поэтому ненадежно для асимптотического вывода), в этом случае кажется, что на самом деле не имеет значения, какой из них вы выберете, но это важнее сосредоточиться на том, как вы собираетесь получить доступ к переменной позже в программе.
Вы пометили «глобальные переменные». Вы пробовали это?