счетчик в рекурсивной функции

#python #recursion

#питон #рекурсия

Вопрос:

У меня есть следующая рекурсивная функция в python:

 def _floodfill(matrix, x, y, counter):  if matrix[x][y] != 9:  matrix[x][y] = 9  counter  = 1  # recursively invoke flood fill on all surrounding cells:  if x gt; 0:  counter  = int(_floodfill(matrix, x - 1, y, counter) or 0)  if x lt; len(matrix) - 1:  counter  = int(_floodfill(matrix, x   1, y, counter) or 0)  if y gt; 0:  counter  = int(_floodfill(matrix, x, y - 1, counter) or 0)  if y lt; len(matrix[0]) - 1:  counter  = int(_floodfill(matrix, x, y   1, counter) or 0)  return counter

Я хочу подсчитать, как часто вызывается эта функция, соответственно подсчитать, сколько чисел != 9 в регионе. Используя следующую матрицу и вызывая функцию, например: _floodfill(matrix,1,1,0) функция должна возвращать 2:

 [[9,9,9],  [9,2,9],  [9,3,9],  [9,9,9]]

в чем проблема с моим кодом?

РЕДАКТИРОВАТЬ Я думаю, что функция более читабельна, как это:

 def _floodfill(matrix, x, y, counter):  if matrix[x][y] != 9:  matrix[x][y] = 9  counter  = 1  # recursively invoke flood fill on all surrounding cells:  if x gt; 0:  counter  = _floodfill(matrix, x - 1, y, counter)  if x lt; len(matrix) - 1:  counter  = _floodfill(matrix, x   1, y, counter)  if y gt; 0:  counter  = _floodfill(matrix, x, y - 1, counter)  if y lt; len(matrix[0]) - 1:  counter  = _floodfill(matrix, x, y   1, counter)  return counter  else:  return 0

1. Вы это проверяли? Я сомневаюсь, что вы можете получить правильные подсчеты таким образом. В большинстве случаев вы return counter ; затем вы используете это возвращаемое значение в a counter = _floodfill(...) . Таким образом, counter по крайней мере удваивается с каждым рекурсивным вызовом.

Ответ №1:

Три замечания:

Вам не нужно counter переходить к рекурсивным вызовам. Для чего им это может понадобиться? counter содержит количество ранее посещенных ячеек. Вашим рекурсивным вызовам не нужно знать, сколько ячеек вы уже посетили. Эта информация движется в обратном направлении: вы хотите, чтобы ваши рекурсивные вызовы сообщали вам, сколько ячеек они посещают.
Гораздо проще написать функцию и использовать ее, если все ветви в an if/else имеют одинаковое return значение. Если функция иногда возвращает количество посещенных ячеек, но иногда возвращает None , ее будет очень неудобно использовать; обратите внимание, как вам приходилось добавлять int(...) or 0 после каждого рекурсивного вызова, чтобы исправить эту проблему.
То, как ваша матрица хранится в виде списка списков, для меня имеет больше смысла индексировать строки y и столбцы, x чем наоборот.

 def _floodfill(matrix, y, x):  if matrix[y][x] == 9:  return 0  else:  matrix[y][x] = 9  counter = 1  if x gt; 0:  counter  = _floodfill(matrix, y, x - 1)  if x lt; len(matrix) - 1:  counter  = _floodfill(matrix, y, x   1)  if y gt; 0:  counter  = _floodfill(matrix, y - 1, x)  if y lt; len(matrix[0]) - 1:  counter  = _floodfill(matrix, y   1, x)  return counter  mat = [  [9,9,9],  [9,2,9],  [9,3,9],  [9,9,9] ]  c = _floodfill(mat, 1, 1) print(c) print(mat)  # 2 # [[9, 9, 9], [9, 9, 9], [9, 9, 9], [9, 9, 9]]

Ответ №2:

Используйте список для сохранения счетчика, так как значения int передаются по значению:

 def _floodfill(matrix, x, y, counter):  if matrix[x][y] != 9:  matrix[x][y] = 9  counter[0]  = 1  # recursively invoke flood fill on all surrounding cells:  if x gt; 0:  _floodfill(matrix, x - 1, y, counter)  if x lt; len(matrix) - 1:  _floodfill(matrix, x   1, y, counter)  if y gt; 0:  _floodfill(matrix, x, y - 1, counter)  if y lt; len(matrix[0]) - 1:  _floodfill(matrix, x, y   1, counter)  return counter  else:  return 0

 _floodfill([[9,9,9],  [9,2,9],  [9,3,9],  [9,9,9]], 1, 1, [0])