재귀 - 자기를 부르는 함수

마트료시카를 열면 같은 모양의 더 작은 인형이 나온다. 그걸 또 열면 또 나온다. 언젠가는 열리지 않는 인형이 나오고, 거기서 멈춘다.

열면 같은 모양이 나온다

재귀가 어렵게 느껴지는 이유는 대개 코드부터 봐서다. 문제 쪽에서 보면 훨씬 간단하다.

폴더 하나의 전체 용량을 구한다고 하자. 폴더 안에는 파일도 있고 폴더도 있다. 안쪽 폴더의 용량은 어떻게 구할까. 똑같이 구하면 된다. 파일도 있고 폴더도 있으니까.

문제를 풀다가 같은 문제가 더 작은 크기로 다시 나오면, 그게 재귀로 풀 수 있다는 신호다. 코드는 그 구조를 그대로 옮긴 것뿐이다.

long size(File dir) {
    long total = 0;
    for (File f : dir.listFiles()) {
        total += f.isDirectory() ? size(f) : f.length();
    }
    return total;
}

size 안에서 size를 부른다. 이상해 보이지만 하는 말은 하나다. “안쪽 폴더는 나한테 다시 물어라.”

필요한 건 둘뿐이다

재귀를 쓰려면 두 가지가 있어야 하고, 없으면 반드시 무너진다.

하나는 더 이상 안 쪼개지는 경우다. 마트료시카의 맨 안쪽 인형. 위 코드에서는 폴더가 아닌 파일이 그것이고, 파일을 만나면 자기를 다시 부르지 않고 크기를 그대로 돌려준다. 이걸 종료 조건 또는 기저 조건이라 부른다.

다른 하나는 반드시 작아진다는 보장이다. 자기를 부를 때 넘기는 문제가 확실히 더 작아야 한다. 안쪽 폴더는 바깥 폴더보다 항상 작으니 언젠가 파일만 남는다.

이 둘 중 하나만 빠져도 알고리즘의 첫 조건인 “반드시 끝난다”가 깨진다.

long size(File dir) {
    long total = 0;
    for (File f : dir.listFiles()) {
        total += size(f);        // 파일도 다시 부른다. 바닥이 없다
    }
    return total;
}

한 줄 차이인데 이건 끝나지 않는다. 그리고 이 상태에서 나는 에러는 StackOverflowError다. **“코드가 틀렸다”가 아니라 “쌓을 자리가 없다”**라고 나오기 때문에, 원인을 종료 조건에서 찾을 생각을 못 하는 일이 흔하다.

쌓을 자리는 한정되어 있다

왜 자리가 없다고 할까. 함수를 부르면 돌아올 위치와 지역 변수가 어딘가에 쌓이기 때문이다. 재귀는 아직 안 끝난 호출을 계속 쌓아 올린다.

함수 호출이 곧 스택이고, 그 스택이 메모리에서 차지하는 자리는 정해져 있다. 보통 수십만 번 정도에서 넘친다.

그래서 재귀 깊이가 입력에 비례해서 깊어지는 코드는 위험하다.

• 연결리스트를 재귀로 훑으면 깊이가 원소 수만큼이다. 100만 개면 터진다.
• 균형 잡힌 트리를 재귀로 훑으면 깊이가 log n이다. 100만 개라도 스무 번이라 안전하다.
• 한쪽으로 쏠린 트리는 깊이가 원소 수만큼이 된다. 트리라고 안심할 수 없는 이유다.

답은 올라오면서 만들어진다

재귀를 처음 볼 때 가장 많이 어긋나는 그림이 이거다. 계산은 내려가면서 일어나지 않는다.

내려갈 때 하는 일은 문제를 더 작게 만들어 넘기는 것뿐이다. 실제 값은 맨 바닥에서 처음 정해지고, 그게 위로 올라오면서 합쳐진다. 폴더 용량도 그렇다. 가장 안쪽 파일 크기가 먼저 정해지고, 그 합이 위로 전달되고, 또 합쳐져서 맨 위 폴더의 용량이 된다.

이 그림이 잡히면 디버깅이 달라진다. 재귀 함수 안에 로그를 찍을 때는 들어갈 때와 나올 때를 둘 다 찍어야 한다. 들어갈 때만 찍으면 문제가 어떻게 쪼개졌는지는 보이는데 답이 어디서 잘못 합쳐졌는지는 안 보인다.

재귀가 쉬워지는 자리, 어려워지는 자리

재귀는 만능이 아니라 잘 맞는 모양이 있다.

잘 맞는 경우는 데이터 자체가 중첩되어 있을 때다. 폴더 안의 폴더, JSON 안의 JSON, 댓글의 답글, 조직도의 하위 조직. 이런 건 반복문으로 짜면 “지금 몇 층인지” 기억할 장치를 손으로 만들어야 하는데, 재귀로 짜면 그 장치를 함수 호출이 대신 해 준다.

안 맞는 경우는 단순히 순서대로 도는 일이다. 목록을 한 바퀴 도는 걸 재귀로 짜면 읽기만 어려워지고 스택만 쌓인다. 반복문이면 되는 걸 재귀로 짜는 건 손해다.

그리고 재귀에는 값이 잘 안 보이는 대가가 있다.

• 호출 자체가 공짜가 아니다. 반복문 한 바퀴보다 함수 호출 한 번이 비싸다.
• 스택 추적이 길어진다. 예외가 터졌을 때 로그가 수백 줄이 되어 진짜 원인을 덮는다.
• 같은 걸 여러 번 다시 계산할 수 있다. 이건 다음다음 글에서 따로 볼 만큼 큰 문제다.

반복문으로 바꿀 수 있나

원리상 모든 재귀는 반복문으로 바꿀 수 있다. 함수 호출이 대신 해 주던 “어디까지 갔는지”를 직접 들고 있으면 된다. 즉 스택을 손으로 만드는 것이다.

바꾸는 게 값을 하는 경우는 둘이다. 깊이가 너무 깊어 터질 때, 그리고 호출 비용이 문제가 될 만큼 자주 돌 때. 그 외에는 대개 재귀 쪽이 읽기 쉽고, 읽기 쉬운 것도 값이다.

⚠️ 마지막 동작이 자기 호출뿐인 형태를 꼬리 재귀라 하고, 이건 컴파일러가 반복문으로 바꿔 줄 수 있다. 다만 자바와 파이썬은 이 최적화를 하지 않는다. “꼬리 재귀로 짰으니 안 터진다”는 말은 언어를 확인하고 해야 한다.

실무에서: 재귀는 데이터 모양을 따라간다

실무에서 재귀를 직접 쓰는 자리는 정해져 있다. 다루는 데이터가 자기 안에 자기를 담고 있을 때다.

• 설정 파일이나 API 응답을 훑어 특정 키를 찾는 일. JSON은 객체 안에 객체가 있어서 깊이를 미리 모른다.
• 카테고리·조직도·댓글처럼 부모가 자식을 갖는 구조. DB에서 한 번에 못 가져오면 재귀 호출이 되고, 그러면 요청이 깊이만큼 늘어난다.
• 디렉터리를 훑는 일. 여기서는 심볼릭 링크가 순환을 만들 수 있어서, 그래프에서 하던 것처럼 방문한 곳을 표시해 두지 않으면 영원히 돈다.

두 번째가 실무에서 특히 아프다. 카테고리 트리를 재귀로 조회하면 깊이만큼 쿼리가 나간다. 코드는 깔끔한데 DB 왕복이 수십 번이 되고, 이건 계산량 문제가 아니라 왕복 횟수 문제라 프로파일러에도 잘 안 잡힌다. 이럴 때는 재귀를 없애는 게 아니라 한 번에 다 가져와 메모리에서 재귀하도록 순서를 바꾼다.

정리

• 재귀는 같은 문제가 더 작은 크기로 다시 나올 때 그 구조를 그대로 옮긴 것이다.
• 필요한 건 둘이다. 안 쪼개지는 경우와 반드시 작아진다는 보장. 하나만 빠져도 안 끝난다.
• 끝나지 않으면 나는 에러는 “쌓을 자리가 없다”다. 원인은 종료 조건에 있는데 메시지는 메모리를 가리킨다.
• 계산은 내려가면서가 아니라 올라오면서 일어난다. 로그는 들어갈 때와 나올 때 둘 다 찍는다.
• 잘 맞는 자리는 데이터가 중첩된 곳이다. 순서대로 도는 일에 쓰면 손해다.
• 실무의 함정은 깊이보다 깊이만큼 나가는 쿼리다. 다 가져와서 메모리에서 재귀하는 쪽으로 바꾼다.

다음 글은 재귀가 가장 크게 값을 하는 꼴을 본다. 쪼개서 풀고 합치기, 그리고 n log n이 어디서 나오는지다.