Node에서 크래시를 일으키는 정확한 재귀 깊이를 찾았습니다

재귀 호출 스택 오버플로우 한계점 찾기 및 반복문(Iteration) 사용의 중요성

• 순수 재귀(Plain recursion)는 기본 스택에서 정확히 9,275호출 깊이에서 충돌했습니다.

• 반복적 리라이트(iterative rewrite)는 크래시 위험 없이 200만 노드 목록을 13.37ms 만에 순회했습니다.

• 이는 재귀가 포기한 지점보다 215배 더 깊은 수치입니다.

• 단순한 while 루프 하나가 테스트에서는 잘 작동했지만 실제 운영 환경(production)에서 실패했던 함수를 대체했습니다.

재귀 호출이 충돌하는 정확한 지점을 제 기계에서 측정할 때마다 항상 9,275호출 깊이였습니다. 저는 "깊은 재귀에 주의하세요"라는 일반적인 조언 대신 실제 수치를 원했기 때문에, 정확한 크래시 포인트를 찾아내는 이진 탐색(binary search)을 작성하여 실행했습니다. 이 숫자가 무엇을 의미하며 실제로 언제 중요한지 설명합니다.

정확한 수치 찾기

사람들이 스택 오버플로우에 대해 배우는 일반적인 방법은 우연히 겪는 것입니다. 재귀 함수는 테스트 데이터에 대해서는 잘 작동하고 배포되지만, 아무도 테스트하지 않은 데이터셋을 만나면 몇 주 후에 충돌합니다. 저는 저를 찾아오기를 기다리는 대신 실제 경계(boundary)가 궁금했습니다.

그래서 노드당 한 번의 호출로 연결 리스트(linked list)를 재귀적으로 순회하는 함수를 작성했고, 길이가 다른 목록들을 만들면서 정확히 어디서 깨지는지 찾았습니다:

function recursiveSum(node, depth) {
  if (!node) return { sum: 0, maxDepth: depth };
...

둥근 숫자를 추측하기보다는, 저는 크래시 포인트 자체를 이진 탐색했습니다. 길이가 N인 목록을 만들고 재귀 순회를 시도하며, 살아남으면 더 큰 것을 시도하고, 오류가 발생하면 더 작은 것을 시도하는 방식입니다. 15번 정도의 반복 끝에 추정치가 아닌 정확한 경계를 얻었습니다.

이 스택에서 그 경계는 9,275호출이었습니다. 9,000이 아니었고, "약 10,000"도 아니었습니다. 정확히 9,275였으며, 동일 프로세스에서 여러 번 실행해도 반복되었습니다.

매번 같은 숫자였습니다. 전혀 불안정하지 않았습니다(No flakiness).

이러한 정밀도는 결과의 형태만큼 중요하지 않습니다. 이 숫자는 사용자의 기계, 런타임 환경(runtime), 그리고 Node를 사용하는지 브라우저 탭을 사용하는지에 따라 다를 것입니다. 변하지 않는 것은 그 숫자가 존재하며, 유한하고, 테스트 데이터가 얼마나 깊었는지로 추측하는 것보다 거의 확실히 작다는 점입니다.

Node는 --stack-size 플래그를 사용하여 이 값을 조정할 수 있게 해주는데, 이는 참신한 트릭인 동시에 함정이기도 합니다. 제한을 높이면 함수가 같은 벽에 부딪히기까지 조금 더 오래 생존합니다. 하지만 이 벽 자체를 제거하는 것은 아닙니다. 단지 아직 테스트하지 않은 곳으로 그 위치를 옮길 뿐입니다.

저는 이번 테스트에서는 의도적으로 해당 플래그를 건드리지 않았습니다. 기본값을 유지하고 싶었기 때문입니다. 왜냐하면 사용자가 특별히 변경하지 않았다면, 코드는 기본값 하에서 프로덕션 환경에서 실행되기 때문입니다.

아예 제한이 존재하는 이유

JavaScript 엔진은 대부분의 언어와 마찬가지로 각 스레드에 고정된 양의 스택 메모리를 할당합니다. 모든 함수 호출은 새로운 프레임을 이 스택 위에 쌓습니다: 인자(arguments), 지역 변수(local variables), 반환 주소(return address)가 포함됩니다. 그 안에서 또 다른 함수를 호출하면, 그 위에 또 하나의 프레임이 쌓입니다. 그리고 반환되면, 그 프레임은 사라집니다.

재귀(Recursion)는 기본 사례(base case)에 도달할 때까지 계속해서 프레임을 쌓기만 하고 제거하지 않습니다. 반복문(Loop)은 그렇지 않습니다. 이것이 전체 차이점이며, 동시에 크래시가 발생하게 된 근본적인 이유입니다.

9275개의 프레임은 호출당 소모되는 스택 공간으로 볼 때 많지 않은 양처럼 들리지만, 실제로도 그렇지 않습니다. 이 함수 내의 각 프레임은 단지 참조(reference)와 숫자만 포함하는 아주 작은 크기입니다. 만약 지역 변수가 더 많거나, 인자가 더 많거나, 또는 각 단계마다 호출 체인이 더 깊은 재귀 함수라면, 수천 번이 아닌 수백 번 정도에서 훨씬 빨리 자신의 벽에 부딪힐 것입니다. 저는 오직 이 하나의 형태만 테스트했습니다. 사용자의 코드는 9275가 아니라 2000번의 호출 깊이에서 크래시가 날 수도 있으며, 측정 방식을 동일하게 적용하지 않으면 알 방법이 없습니다.

꼬리 재귀 최적화(Tail-call optimization, TCO)는 이론적으로 이것을 해결해야 합니다. 왜냐하면 마지막 동작이 자신을 호출하는 함수는 기술적으로 자신의 프레임을 유지할 필요가 없기 때문입니다. Node와 Chrome의 엔진인 V8은 이를 구현하지 않습니다. 이는 버그 보고서라기보다는 오늘날 코드를 작성하고 있는 현실 그 자체이므로,

그것은 명세(spec)에 있습니다. 다만 실제로 실행하는 엔진에는 그 내용이 없을 뿐입니다. 이처럼 명세가 허용하는 것과 실제 엔진이 동작하는 것 사이의 간극이야말로, 그것에 대해 읽는 것이 아니라 실제 것을 테스트할 때만 드러나는 바로 그런 종류의 세부 사항입니다.

반복적 재작성(The Iterative Rewrite), 시간 측정

해결책은 거의 모욕적으로 간단합니다.

재귀 호출을 루프(loop)로 대체하면, 더 이상 쌓아 올릴 것이 없기 때문에 호출 스택(call stack)이 완전히 커지는 것을 막을 수 있습니다:

function iterativeSum(head) {
  let count = 0;
...

저는 이것을 2,000,000개의 노드 목록에 대해 실행했는데, 이는 재귀 버전이 포기했던 지점보다 215배 더 깊은 곳입니다. 이 작업은 13.37밀리초 만에 완료되었습니다. 충돌도 없고, 특별한 처리도 없으며, 최선을 바라는 마음으로 try/catch로 감쌀 필요도 없습니다.

이 부분이 주목할 만합니다. 재귀 버전은 충돌하기 직전까지 느려진 것이 아니라, 어느 순간부터 갑자기 문제가 생긴 것입니다. 스택이 가득 차고 있다는 경고를 점진적으로 주는 것이 아닙니다. 작동하다가, 작동하다가, 작동하다가 하다가, 우연히 테스트했던 것보다 더 긴 입력에 대해서는 RangeError: Maximum call stack size exceeded 오류를 발생시킵니다.

반면 반복적인 버전은 그 절벽(cliff)을 입력 크기에 비례하고 다른 어떤 것에 의존하지 않는 평평하고 지루하며 예측 가능한 비용으로 바꿉니다. 2백만 개의 노드에 대해 13밀리초는 승리의 축배가 아니라, while 루프가 무언가를 세라고 요청받았을 때 하는 단순한 동작일 뿐입니다. 우아함은 필요하지 않습니다.

저는 또한 절반 옵션, 즉 호출 스택 대신 배열에 작업을 푸시하여 수동으로 관리하는 스택(manually managed stack)도 시도해 보았습니다. 이를 통해 실제로 재귀하지 않으면서도 재귀적 사고방식을 유지할 수 있습니다. 이것은 작동하며, 일반적인 루프를 사용하기에는 어색한 트리 순회(tree traversal)의 경우 합리적인 패턴입니다. 하지만 이처럼 직선적인 선형 이동(straight linear walk)의 경우에는 위 while 루프에 비해 얻는 이점이 없는 추가 코드일 뿐입니다. 재귀의 형태가 실제로 가치를 발휘하는 경우, 예를 들어 평평한 목록 대신 가지를 가진 트리를 순회할 때만 아껴두세요.

제가 실제로 이것을 사용할 경우

대부분의 재귀 함수는 이 모든 것이 중요해질 만큼 깊이 내려가지 않습니다. 작고 유한한 트리 위에서 재귀하거나, 몇 개의 중첩된 설정 레벨을 탐색하거나, 짧은 파싱 루틴을 수행하는 경우 등은 9,275 프레임에는 한참 못 미칩니다. 저는 그런 것들은 코드가 더 읽기 좋고 위험도가 거의 제로에 가깝기 때문에 계속 재귀적으로 작성할 것입니다.

위험성은 특히 재귀 깊이가 사용자 통제 가능하거나 예측 불가능한 입력의 크기에 묶여 있을 때 나타납니다. 데이터베이스 행으로 구축된 연결 리스트, 업로드된 파일을 탐색하는 파서, 다른 사람이 생성한 중첩 JSON으로 만들어진 트리 등이 그렇습니다. 이 모든 경우에 깊이는 사용자가 선택한 것이 아니라 데이터가 결정해 준 것이며, 항목 12개짜리 테스트 피처로는 40만 개를 포함하여 누군가가 업로드할 파일에 대해 아무것도 알려주지 못합니다.

답글이 달린 답글로 이루어진 댓글 스레드에서 만들어진 트리는 같은 형태입니다. 대부분의 스레드는 얕습니다. 하지만 누가 한계를 테스트하거나 스크립트가 생성했기 때문에 응답이 15,000개까지 깊어지는 그 하나의 스레드가 사용자 앞에서, 최악의 시점에 당신의 충돌 지점을 찾아낼 것입니다.

진짜 교훈은 구체적인 숫자가 아니라 이겁니다. 9,275는 오늘날 제 기계에 대한 사실일 뿐입니다. 중요한 습관은 함수의 재귀 깊이가 사용자가 통제하는 것과 그렇지 않은 것에 의해 제한되는지 확인하고, 배포된 후에 정확히 테스트할 생각을 못 했던 입력으로 충돌하기 전에 '통제 불가능한' 경우를 리팩토링 하는 것입니다.

이것을 프로덕션 사고가 되기 전에 확인할 수 있는 저렴한 방법이 있습니다. 재귀 함수에 사용해 온 모든 테스트 피처를 가져와서 그 크기에 100을 곱하세요. 그렇게 큰 피처가 주변에 없다면, 하나를 생성하세요. 사용자가 실수로 대신 해 주기 전에, 의도적으로 한 번 이 함수를 실행해 보세요.

파일 업로드, 크기 미지인 API 응답, 또는 사용자 생성 중첩 구조와 관련된 모든 것에는 더 많은 노력을 기울여야 합니다. 테스트를 작성할 때 처음부터 터무니없이 큰 입력을 사용하세요. 충돌 보고서를 받은 후에 생각하는 것이 아닙니다. 백만 개의 노드 목록을 생성하는 데는 5분밖에 걸리지 않습니다. 하지만 운영 환경에서 새벽 2시에 RangeError가 발생하고, 아무도 작은 테스트 파일이 있는 노트북으로 재현할 수 없는 이유를 알아내는 것은 훨씬 오래 걸립니다.

이는 버그가 어디서 시작했는지 추측하는 대신 1,000개의 실제 커밋에 걸쳐 git bisect 실행하기를 하거나, CSS 속성이 명세서가 암시하는 대로 작동한다고 가정하는 대신 3,000개의 카드에 걸쳐 content-visibility가 실제로 어떻게 변경되었는지 측정하기를 하는 것과 같은 규율입니다. 함수의 형태나 성능에 대한 추측을 믿지 마세요. 테스트 데이터보다 더 큰 것을 공급했을 때 무슨 일이 일어나는지를 신뢰하세요. 추측은 빠릅니다. 하지만 최악의 시간에 운영 환경 충돌 디버깅을 하게 만드는 방법이기도 합니다.

핵심 요약 (Bottom Line)

제 스택에서의 일반적인 재귀(Plain recursion)는 제가 측정할 때마다 정확히 9,275 호출에서 깨졌고, 동일한 로직의 반복문(iterative rewrite)은 아무것도 충돌하지 않는 상태로 그 깊이의 215배를 13.37밀리초 만에 처리했습니다. 숫자 9,275는 귀하의 기계나 함수로 옮겨갈 수 없으니 규칙으로 복사하지 마세요. 전해지는 것은 방법입니다. 만약 함수의 재귀 깊이가 파일 크기, 행 개수 또는 사용자가 생성한 중첩과 같이 통제할 수 없는 무언가에 의존한다면, 사용자가 하기 전에 실제 깨지는 지점을 찾아야 합니다. 반복문은 가독성 측면에서 이미 비용을 치른 재귀와는 달리 아무것도 비용이 들지 않으며, 나중에 패치할 수 없는 유일한 실패 모드를 되찾아 줍니다.