글 읽기 - python에서 재귀함수 부를 수 있는 깊이가 어느정도인가요?

shjoo840 6년 전 0

이 문제는 치즈 내부의 빈 공간과 치즈 외부를 구분해야 풀 수 있습니다.

치즈 외부를 flood fill (외부의 한 점에서 시작. 상하좌우로 이동하며 빈공간을 표시하는 방법)으로 체크하려고 했는데 런타임 에러가 뜨더군요.

이 문제의 가로 세로 최대 사이즈가 100이라서 치즈가 거의 없어지면 재귀함수 콜을 10000번정도 해야 하고 이 때문에 에러가 나온 것 같습니다.

재귀함수 사용할 때 마다 런타임 에러가 자주 나와서 그런데 아래 3개 질문에 답변해주실 수 있나요?

1. 파이썬에서 재귀함수 콜이 가능한 횟수

2. 재귀함수 콜 가능 횟수가 제한되어 있는 이유

3. 다른 언어도 재귀함수 콜 가능 횟수가 정해져있는지

감사합니다!

소스코드는 질문과 상관은 없지만 첨부합니다.

n, m = map(int, raw_input().split())
A, B = [], []
for i in range(n):
    A.append(map(int, raw_input().split()))
for i in range(n):
    B.append([0]*m)
    
def x(a, b):
    if A[a][b] == 0:
        B[a][b] = -1
        if a>0 and B[a-1][b] == 0:
            x(a-1, b)
        if a<n-1 and B[a+1][b] == 0:
            x(a+1, b)
        if b>0 and B[a][b-1] == 0:
            x(a, b-1)
        if b<m-1 and B[a][b+1] == 0:
            x(a, b+1)
        return 
    else:
        B[a][b] = 1
        return 
cheese=1
itr=0
rmch = 0
while cheese - rmch:
    itr += 1
    cheese = rmch = 0
    for i in range(n):
        for j in range(m):
            B[i][j] = 0
    x(0,0)
    for i in range(n):
        for j in range(m):
            if A[i][j] == 1:
                cheese += 1
                if B[i][j] == 1:
                    A[i][j] = 0
                    rmch += 1
            B[i][j] = 0
print itr
print cheese

kimminsu38oo 2년 전 0

1.구글에 검색해 보니 1000번 정도로 제한되어 있네요

2.재귀함수는 stack방식으로 쌓이는데 stack방식으로 1000번을 쌓는건 굉장히 연산횟수가 많아지기 때문입니다. 실제로 함수로 500번정도만 쌓아도 작업관리자에서 연산횟수가 크게

늘어남을 볼 수 있습니다.

3.네 프로그램이 강제 종료됩니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python에서 재귀함수 부를 수 있는 깊이가 어느정도인가요?

shjoo840 6년 전 0

kimminsu38oo 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말