Python에서는 sys 라이브러리의 setrecursionlimit() 메소드를 사용해 재귀 깊이 제한을 설정할 수 있는데,
Java에서도 같은 작업이 가능할까?
결론부터 말하자면, 그런 API는 Java에 존재하지 않는다.
다만, 이 글을 찾아온 사람이라면 궁금해 할 만한 내용을 소개하고자 한다.
재귀, 얼마나 깊게 할 수 있을까?
Java에서 재귀 깊이 제한이라는 용어가 따로 있는지는 모르겠지만, 편의상 '런타임 에러를 일으키지 않는 재귀 호출 횟수의 최댓값'이라는 의미로 사용하겠다. (Python에서 재귀 깊이 제한은, 런타임 에러를 일으키기 위해 프로그래머가 명시적으로 설정할 수 있다는 점에서 다르다)
우선 재귀 깊이 제한은 JVM의 스택 메모리와 깊은 관련이 있다.
JVM 스택 메모리의 크기 ↓, 재귀 함수가 차지하는 메모리의 양 ↑
=> 재귀 깊이 제한 ↓
JVM이 프로그램의 실행을 위해 스택 메모리를 써야 하는데, 더 이상의 여유 공간이 없을 때 발생시키는 런타임 오류가 바로 StackOverflowError라는 점을 떠올려 보면 이같은 관련성을 이해할 수 있다.
프로그램이 실행되는 환경에 따라 다를 것이므로, 일단 아래의 코드를 실행해서 몇 번째 재귀 호출에서 스택 오버 플로우가 발생하는지 확인해 보자.
public class Test {
static int callCnt;
public static void main(String[] args) {
long cntSum = 0;
for (int t = 1; t <= 5; t++) {
callCnt = 0;
try {
foo();
} catch (StackOverflowError e) {
System.out.printf("#%d : %d번째 함수 호출에서 스택 오버플로우 발생\n", t, callCnt);
cntSum += callCnt;
}
}
long cntAvr = cntSum / 5;
System.out.printf("평균 %d번째 함수 호출에서 스택 오버플로우 발생", cntAvr);
}
static void foo() throws StackOverflowError {
callCnt++;
foo();
}
}
foo() 함수의 호출 횟수는 실행할 때마다 다른 값이 나오지만, 여기서는 편의상 4만 회라고 가정하자.
여기서 의문점이 든다. 알고리즘 문제를 풀면서 트리의 깊이 우선 탐색(DFS)을 재귀 함수로 구현했는데, 만약 탐색할 트리가 노드 10만 개로 이루어진 경사 트리라면 어떻게 될까? 약 4만 번째 노드를 방문하는 도중에 StackOverflowError를 만나서 프로그램이 종료될 것이다. 심지어 dfs 함수는 적어도 foo 함수보다는 더 많은 로컬 변수와 함께 더 많은 명령을 수행할 것이므로, 재귀 함수 하나가 메모리에서 차지하는 공간은 훨씬 클 것이다. dfs 함수는 4만 개의 노드도 방문하지 못할 것 같다.
그렇다면 지금이라도 깊이 우선 탐색의 구현 방법을 재귀에서 스택으로 바꿔야 할까?
다행히 그럴 필요는 없다.
재귀, 어떻게 더 깊게 할 수 있을까?
JVM의 옵션을 설정하여, 스택 메모리의 크기를 넉넉하게 늘리면 된다. 지금까지의 고민은 백준 채점 환경에서는 할 필요가 없는 것이다. 아래는 백준 온라인 채점 사이트의 Java 8 버전 실행 환경이다.
각 옵션의 기능은 다음과 같다.
- Xms1024m : 초기 Heap size를 1024MB로 설정한다
- Xmx1920m : 최대 Heap size를 1920MB로 설정한다
- Xss512m : 각 Thread에 할당되는 Stack size를 512MB로 설정한다
스택 메모리의 크기가 512MB이면, 재귀 호출 횟수가 얼마나 많아진 걸까?
실험을 위해, 같은 옵션을 로컬 환경에도 적용해 보자
1. IntelliJ
2. Eclipse
자 이제 foo() 함수를 최대한으로 재귀 호출 하자.
스택 메모리의 크기를 512MB로 설정한 효과는 대단했다. 백준 사이트에 재귀를 사용한 풀이를 제출할 때, 기저 조건(재귀 호출을 중단하는 조건)을 잘 잡았다면, 스택 오버플로우는 걱정하지 않아도 된다. 단, 무거운 재귀 함수의 호출이 '해당 문제의 메모리 제한'을 초과하지 않도록 신경써야 한다.