꼬리 재귀 최적화

hwhyeons·2025년 6월 23일

이전에 파이썬의 재귀 호출 제한에 대한 내용을 찾아보고 글을 작성하면서,

꼬리 재귀 함수 최적화에 대한 것에 대해 더 깊게 공부하게 되었다.

재귀함수 vs 반복문

일부 재귀함수는 반복문으로 변경할 수 있다.

가장 대표적인 예시로 Factorial 함수가 있다.

간단하게 Python코드로 확인해보면

# 재귀함수
def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial_recursive(n - 1)

# 반복문
 def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

같은 동작을 재귀함수로 구현했을 때와 반복문으로 구현했을 때는
성능, 안정성의 차이가 발생한다.

개인적으로 가독성은 재귀함수가 좀 더 좋다고 생각하지만,
성능이나 안정성 면에서는 반복문으로 구현하는 것이 더 낫다.

재귀 함수의 경우 호출마다 스택 프레임을 생성하기 때문에
메모리 측면, 속도 측면에서 반복문에 비해 모두 불리하다.

또한, 재귀 함수의 경우 계속 스택 프레임을 생성하기 때문에 스택오버플로우 발생 가능하다.

나는 가독성과 구현의 편의성 때문에 알고리즘 문제를 풀 때 재귀함수를 굉장히
자주 사용한다.

하지만 백준 문제를 파이썬으로 주로 푸는 사람들은 알겠지만,
재귀함수를 자주 쓰게 되면 RecursionError 또는 시간초과, 메모리초과가
발생하는 문제를 매우 자주 볼 수 있다..

대표적으로 DP 문제를 TopDown + 재귀함수 형태로 구현하면 시간초과 나던걸
같은 형태로 반복문으로 바꾸기만 해도 바로 통과하는 경우가 참 많았던 것 같다.

사실 재귀 함수 형태를 반복문으로 바꿀 수 있는 경우가 있고
C,C++ 등의 컴파일러는 자동으로 최적화 해주기도 한다.

재귀 함수 형태가 꼬리 재귀 형태면 반복문으로 최적화가 가능하다.

꼬리 재귀란?

꼬리 재귀란, 함수가 자기 자신을 호출한 직후,
더 이상 아무 작업도 하지 않고 곧바로 리턴하는 구조를 의미한다.

팩토리얼 코드로 직접 비교해보는게 편하다.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

꼬리 재귀가 될 조건이 함수가 자기 호출하고 아무 작업을 하지 않는다라고 말했는데, 위 코드는 함수가 자기 자신을 호출하고나서 n을 곱하는 연산을 수행한다.
즉, 이는 꼬리 재귀 형태가 아니다.

그러면 위 팩토리얼 함수를 꼬리 재귀 형태로 바꾼 코드는 무엇일까?

def tail_recursive_example(n, acc=1):
    if n == 0:
        return acc
    return tail_recursive_example(n - 1, n * acc)

tail_recursive_example()를 재귀 호출 하고나서 바로 리턴한다.
추가 연산이 없다.

꼬리 재귀 최적화 원리

그러면 재귀 호출시에 추가 연산이 없는 것과 최적화를 하는 것이랑 무슨 연관일까?

바로바로 리턴을 한다고 했는데, 그렇기 때문에 내용을 저장하고 있을 필요가 없다.

꼬리 재귀는 함수가 자신을 호출한 뒤 더 이상 할 일이 없기 때문에,
현재 스택 프레임을 버리고 다음 호출로 재사용할 수 있다.

즉, 일반 재귀 (꼬리 재귀가 아닌)는 factorial(n-1)을 호출하고나서
다시 n과 곱해야 하기 때문에 스택프레임을 계속 유지해야하지만,
꼬리 재귀 형태는 어차피 최종적으로 리턴만 쭉 연쇄적으로 하면 끝난다.

꼬리 재귀 코드를 다시 한번 자세히 보면

def tail_recursive_example(n, acc=1):
    if n == 0:
        return acc
    return tail_recursive_example(n - 1, n * acc)

일반 재귀 형태와 다르게 acc라는 누적 값을 저장하기 위한 결과를
함수 인자에 넘기는 것을 볼 수 있다.

일반적인 재귀의 경우,
n * factorial(n-1)을 하면
n이 10인 경우를 가정해보면
factorial(10)을 구하려면, factorial(9)를 알아야
factorial(10)을 알 수 있다.

하지만 꼬리 재귀는, acc를 이용해서 함수 깊이가 늘어남과 동시에
누적 값을 계속 갱신하기 때문에
tail_recursive_example(9)가 아니라
tail_recursive_example(0)에 도달하면 이미 정답을 알 수 있다.

즉, 재귀 함수를 호출하고 다시 되돌아오는 과정이 필요 없이
가장 깊은 재귀에 도달했을 때 이미 정답이 도출된다.
그렇기 때문에 일반 재귀 함수 형태처럼 스택 프레임을 유지할 필요가 없다.

반복문으로 factorial을 구현한 형태와 유사하다.

 def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

이 반복문 코드도 result라는 누산기를 이용해서 한단계 한단계씩
누적 값을 갱신한다.

이런 원리로 C,C++ 등의 일부 컴파일러는 꼬리재귀함수를 반복문으로
변경해서 최적화 할 수 있다.

꼬리 재귀 최적화 조건

원리를 이해하다보면, 언제 꼬리 재귀 최적화가 가능한 조건인지 알 수 있다.

재귀 함수를 꼬리 재귀 형식으로 구현
컴파일러가 꼬리 재귀 최적화를 지원할 것

물론 꼬리 재귀 형태를 개발자가 직접 바꿀 수 있지만,
컴파일 기준으로 봤을 때는 당연히 컴파일러 차원에서 꼬리 재귀 최적화를 지원하지 않는다면 의미가 없다.

컴파일러도 형태가 꼬리 재귀 형태가 아닌데 최적화를 하지는 않을 것이다.

실제 최적화 확인

컴파일러가 정말 최적화를 해주는지 궁금해서 테스트 해봤다.

IDE는 CLion을 사용했으며,
M4 맥북으로 작업하였다.

꼬리 재귀 최적화 활성화를 위해서
최적화 활성 상태의 경우 릴리즈 모드와 컴파일러 Flag,
최적화 비활성의 경우 디버그 모드로 테스트했다.

최적화를 위해 CMakeLists.txt에

set(CMAKE_CXX_FLAGS_RELEASE
        "-O2 -fomit-frame-pointer -foptimize-sibling-calls -funwind-tables")

를 추가하였다 (이는 컴파일러나 환경에 따라 다를 수 있음)

확실한 시간체크를 위해 시작 N을 매우 크게 설정하였다.
참고로 N이 너무 커서 숫자 오버플로우로 값은 다르게 나오니
시간만 참고하면 될 것 같다.

long fact_tail(long n, long acc = 1)
{
    if (n == 0) return acc;
    return fact_tail(n - 1, acc * n);
}

int main() {
    auto t0 = std::chrono::steady_clock::now();   // ⏱ 시작
    long val = fact_tail(100000);
    auto t1 = std::chrono::steady_clock::now();   // ⏱ 끝

    /* 경과 시간(ms)만 출력 */
    double ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
    std::cout << "elapsed: " << ms << " ms\n";
    std::cout << "result: " << val << '\n'; 
}

테스트 결과
릴리즈 모드(최적화O) : 0.017~0.019ms
디버그 모드(최적화X) : 0.8~0.9ms

생각보다 차이가 매우 컸다.

혹시 이 속도 차이가 꼬리 재귀 최적화의 문제가 아니라
다른 부분에서 발생한 최적화일 가능성도 있다고 생각되어서,
팩토리얼 함수를 이미 반복문으로 최적화된 형태인

long fact_tail(long n, long acc = 1)   // 이미 최적화된 반복문 버전
{
    while (n) { acc *= n; --n; }
    return acc;
}

으로 실험해보니,
테스트 결과
릴리즈 모드(최적화O) : 0.017~0.02ms
디버그 모드(최적화X) : 0.08~0.09ms

정도로 나왔다.

물론 저 꼬리 재귀 형태말고도 다른 최적화가 동작하기 때문에
반복문 형태로 바꿨다고 해서 릴리즈모드와 디버그 모드의 차이가 없지는 않아도,
디버그모드만 봤을 때는 차이가 10배정도로 매우 크게났다.

사실 최적화가 되었는지 보는 가장 정확한 방법은 어셈블리를 보는 것이다.

최적화 전의 어셈블리 코드의 경우
(참고로 아래 어셈블리 코드에는 chrono로 시간 체크하는 부분은 빼놓고 빌드한 것)
(Clion에서 제공하는 Show Assembly로 나오는 형식임)


fact_tail(long, long):
	sub	sp, sp, #48
	stp	x29, x30, [sp, #32]
	add	x29, sp, #32
	str	x0, [sp, #16]
	str	x1, [sp, #8]
	ldr	x8, [sp, #16]
	cbnz	x8, LBB0_2
	b	LBB0_1
LBB0_1:
	ldr	x8, [sp, #8]
	stur	x8, [x29, #-8]
	b	LBB0_3
LBB0_2:
	ldr	x8, [sp, #16]
	subs	x0, x8, #1
	ldr	x8, [sp, #8]
	ldr	x9, [sp, #16]
	mul	x1, x8, x9
	bl	fact_tail(long, long)
	stur	x0, [x29, #-8]
	b	LBB0_3
LBB0_3:
	ldur	x0, [x29, #-8]
	ldp	x29, x30, [sp, #32]
	add	sp, sp, #48
	ret

_main:
	sub	sp, sp, #32
	stp	x29, x30, [sp, #16]
	add	x29, sp, #16
	stur	wzr, [x29, #-4]
	mov	x0, #10
	mov	x1, #1
	bl	fact_tail(long, long)
	ldp	x29, x30, [sp, #16]
	add	sp, sp, #32
	ret

여기서 눈여겨 볼 부분은
bl fact_tail(long, long)이다.

그러면 릴리즈모드 + flag 활성화로 꼬리 재귀를 활성화하고 빌드한 다음에
다시 어셈블리를 확인해보면


fact_tail(long, long):
	cbz	x0, LBB0_7
	cmp	x0, #4
	b.hs	LBB0_3
	mov	x8, x0
	b	LBB0_6
LBB0_3:
	and	x9, x0, #0xfffffffffffffffc
	and	x8, x0, #0x3
	mov	w10, #1
	mov	x11, x0
	mov	x12, x9
	mov	w13, #1
	mov	w14, #1
LBB0_4:
	sub	x15, x11, #1
	sub	x16, x11, #2
	sub	x17, x11, #3
	mul	x1, x1, x11
	mul	x10, x10, x15
	mul	x13, x13, x16
	sub	x11, x11, #4
	mul	x14, x14, x17
	sub	x12, x12, #4
	cbnz	x12, LBB0_4
	mul	x10, x10, x1
	mul	x10, x13, x10
	mul	x1, x14, x10
	cmp	x9, x0
	b.eq	LBB0_7
LBB0_6:
	mul	x1, x1, x8
	subs	x8, x8, #1
	b.ne	LBB0_6
LBB0_7:
	mov	x0, x1
	ret

_main:
	mov	w0, #24320
	movk	w0, #55, lsl #16
	ret

함수 재귀 호출 부분이 사라졌다.

사실 어셈블리에 대한 지식은 별로 없어서 어셈블리 분석 부분은
GPT의 도움을 좀 받았다.

최적화가 불가능한 추가 경우

이건 GPT에게 질문을 하다보니 알게된 부분이다.

스택프레임을 미리 제거할 수 없는 경우에는 자동 최적화가 안된다고 한다.

int f(int n) {
    std::string tmp = std::to_string(n);   // 생성
    if (n == 0) return 0;
    return f(n-1);                         // tail 위치?
    // └─ NO.  tmp.~basic_string() 가 반환 직전에 반드시 호출돼야 함
}

GPT가 제공해준 코드인데, 함수 리턴 시점에 string()의 소멸자 호출이 필요하므로 최적화가 되지 않는다고 한다.

궁금해서 factorial 코드를

long fact_tail(long n, long acc = 1)
{
    std::string tmp = std::to_string(n);   // 생성
    if (n == 0) return acc;
    return fact_tail(n - 1, acc * n);
}