再帰関数について(呼び出し回数の上限のエラー？)

Question

前提・実現したいこと

再帰関数を用いてLakeCounting問題(孤立した池を数え上げる)を作っていますが、再帰呼出し回数が上限に達した旨のエラーが出ていますが対処できません。

発生している問題・エラーメッセージ

エラーメッセージ
Traceback (most recent call last):
  File "/home/xxx/PIPENV/AtCoder/code/Lake_counting.py", line 27, in dfs
    dfs(x, y)
  File "/home/xxx/PIPENV/AtCoder/code/Lake_counting.py", line 27, in dfs
    dfs(x, y)
  File "/home/xxx/PIPENV/AtCoder/code/Lake_counting.py", line 27, in dfs
    dfs(x, y)
  [Previous line repeated 995 more times]
  File "/home/xxx/PIPENV/AtCoder/code/Lake_counting.py", line 26, in dfs
    if (0 <= nx < col_size) and (0 <= ny < row_size) and LAKE[nx][ny] == 'w':
RecursionError: maximum recursion depth exceeded in comparison

Process finished with exit code 1

コード

import sys

sys.setrecursionlimit(5000)
LAKE = [
    'wwwwwww.',
    'wwww....',
    '.......w']
# strをlistに変換する
for i in range(len(LAKE)):
    for k in range(len(LAKE[0])):
        LAKE[i] = list(LAKE[i])

print(LAKE)

row_size = len(LAKE)
col_size = len(LAKE[0])


def dfs(x, y):
    LAKE[x][y] = '.'

    for dx in [-1, 1]:
        for dy in [-1, 1]:
            nx = x + dx
            ny = y + dy
            if (0 <= nx < col_size) and (0 <= ny < row_size) and LAKE[nx][ny] == 'w':
                dfs(x, y)


def solve():
    res = 0
    for row in range(row_size):
        for col in range(col_size):
            LAKE[row][col] == 'w'
            dfs(row, col)
            res += 1
    return res


print(solve())

試したこと

sys.setrecursionlimit(5000)

を実行し上限を上げましたが結果は変わりませんでした。
また、LAKEの文字列もかなり小さくしましたがエラーが出ています。

以下ご指摘のdfs(x,y)→dfs(nx,ny)などの修正を加えたコードです。

import sys
import logging

logging.basicConfig(level=logging.CRITICAL)

sys.setrecursionlimit(5000)
LAKE = [
    'wwwwwww.',
    'ww......',
    '....w..w']
# strをlistに変換する
for i in range(len(LAKE)):
    LAKE[i] = list(LAKE[i])

logging.info(str(LAKE))

row_size = len(LAKE)
col_size = len(LAKE[0])


def dfs(x, y):
    LAKE[x][y] = '.'

    for dx in [-1,0, 1]:
        for dy in [-1,0, 1]:
            nx = x + dx
            ny = y + dy
            if (0 <= nx < row_size) and (0 <= ny < col_size):
                logging.info('nx:{},ny:{}'.format(nx, ny))

                if LAKE[nx][ny] == 'w':
                    dfs(nx, ny)


def solve():
    res = 0
    for row in range(row_size):

        for col in range(col_size):

            if LAKE[row][col] == 'w':
                # 'w'の部分から再帰関数を開始する
                dfs(row, col)
                # 再帰関数が一段落したら++
                res += 1
    return res


print('lake :', solve())

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[coco_bauer]

プログラムで気になった点

# strをlistに変換する
for i in range(len(LAKE)):
for k in range(len(LAKE[0])):
LAKE[i] = list(LAKE[i])
の部分、ループ変数kで回している内側のforループで、kが使われていません。これでLAKE変数に正しい値が設定されるのでしょうか？

[kimtakuya_]

回答ありがとうございます。
確かめたところ# strをlistに変換する
for i in range(len(LAKE)):
LAKE[i] = list(LAKE[i])
の部分だけで動作していたようですが、この部分では正しい値が設定されているようです。

Answer 1

気になる点

def dfs(x, y):
    LAKE[x][y] = '.'

    for dx in [-1, 1]:
        for dy in [-1, 1]:
            nx = x + dx
            ny = y + dy
            if (0 <= nx < col_size) and (0 <= ny < row_size) and LAKE[nx][ny] == 'w':
                dfs(x, y)

関数 defsの定義で、引数、x,yは、この関数の中で参照も変更もされることなく、関数の定義の最後の行で　dfs(x, y)が呼び出されています。
関数が呼び出されたのと同じ条件で、同じ関数を再帰呼び出していますから、無限ループになっているのだと思われます。

最後の行は、 def(x,y) ではなく、 def(nx, ny)を呼び出すべきなのではないでしょうか？

Comments

[coco_bauer]

「この関数の中で参照も変更もされることなく」の部分は、「この関数の中で変更もされることなく」と修正いたします。