PythonでDFSする際にexit status 139が出てしまう

Question

前提

アルゴ式の
https://algo-method.com/tasks/974
の問題を解いている際に一つだけランタイムエラーになってしまいました。

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

exit status 139

該当のソースコード

import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

dist = [-1 for _ in range(n)]
visited = [False for _ in range(n)]
dist[0] = 0


def dfs(v):
    visited[v] = True
    for nv in G[v]:
        if visited[nv]:
            continue
        dist[nv] = dist[v] + 1
        dfs(nv)


dfs(0)
ans = max(dist)
print(ans)

試したこと

解説のもののコピペはうまく動作しました。
解説の記事と同じアルゴリズムのはずなのですがエラーになってしまいます。

エラーの消し方がわかりません。
よろしくお願いします。

Comments

[kk_22]

間違えました、解説はBFSでやってるので同じではないです
が、エラーになるのはよくわかりません

Answer 1

再帰呼び出しが深すぎてクラッシュしているものと思われます。

公式のsys.setrecursionlimitの説明に、以下の記述があります。

limit の最大値はプラットフォームによって異なります。深い再帰処理が必要な場合にはプラットフォームがサポートしている範囲内でより大きな値を指定することができますが、この値が大きすぎればクラッシュするので注意が必要です。

つまり、sys.setrecursionlimitにいくら大きい値を設定しても、プラットフォームがサポートしている上限を超える再帰呼び出しはできない(やろうとするとクラッシュする)ということです。

実際、以下のようにコード先頭部分を改変して実行してみたところ(問題の制限内で、再帰呼び出し回数最大となる入力を生成)、Segmentation Faultが発生しました。

import sys
sys.setrecursionlimit(10 ** 8)
n = 100000
G = [[] for _ in range(n)]
for i in range(n - 1):
	G[i].append(i + 1)
	G[i + 1].append(i)

Comments

[kk_22]

ありがとうございます。ということはAtCoder含めPythonで再帰をやる時にはsys.setrecursion()で回数を決める前に制限について考える必要がありそうですね。