재귀 함수와 꼬리 재귀 최적화

재귀 함수

함수 안에서 자기 자신을 다시 호출하는 함수를 재귀 함수(Recursive Function)라고 한다.

동작 과정: 콜 스택

함수를 호출할 때마다 콜 스택(Call Stack)에는 매개변수, 지역 변수, 반환 주소 등이 스택 프레임으로 저장된다. 함수가 자기 자신을 호출하면 현재 프레임을 스택에 남겨 둔 채, 호출한 함수의 반환을 기다린다.

1. 종료 조건(base case)에 걸리기 전까지 호출할 때마다 프레임이 계속 쌓인다.
2. 종료 조건에 걸리면 가장 위의 프레임부터 하나씩 실행을 마치고 사라진다.

재귀 깊이만큼 프레임이 쌓이기 때문에, 깊이가 깊어지면 스택 오버플로가 일어날 가능성이 크다.

꼬리 재귀 최적화

꼬리 재귀(Tail Recursion)란 재귀 호출이 함수의 마지막 동작인 경우를 말한다. return 문에서 자기 자신을 호출하고, 그 결과에 추가 연산을 하지 않는다.

# 일반 재귀: 호출이 끝난 뒤 n을 곱해야 하므로 프레임을 유지해야 한다
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


# 꼬리 재귀: 호출 결과를 그대로 반환하므로 현재 프레임이 더 필요 없다
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)

꼬리 재귀에서는 호출 이후 남은 연산이 없으므로 현재 프레임을 보존할 이유가 없다. 컴파일러가 이를 반복문처럼 바꿔 콜 스택에 프레임을 더 쌓지 않게 하는 것이 꼬리 재귀 최적화(Tail Call Optimization)이다.

단, 컴파일러나 런타임이 이 최적화를 지원해야 의미가 있다. 지원하지 않는 언어에서는 꼬리 재귀로 작성해도 프레임이 그대로 쌓인다.

언어별 지원

• C++: 주요 컴파일러가 최적화 옵션에 따라 꼬리 호출을 최적화한다.
• JavaScript: ES6 명세에 꼬리 호출 최적화가 포함되었지만, 실제로 구현한 엔진은 일부뿐이다.
• Python: 인터프리터가 직접 지원하지 않는다. 위의 factorial_tail도 깊이가 깊어지면 재귀 한도에 걸린다.
• Java: 직접 지원하지 않는다.

Java가 지원하지 않는 이유

JDK 클래스에는 보안에 민감한 메서드가 있고, 이들은 JDK 라이브러리 코드와 호출 코드 사이의 스택 프레임 개수에 의존한다. 꼬리 재귀 최적화로 스택 프레임 수가 달라지면 이 의존 관계가 깨져 오류가 발생할 수 있다.

대신 Java 8의 람다식과 함수형 인터페이스로 꼬리 재귀와 같은 개념을 적용해 볼 수 있다.