꼬리 재귀

면접을 준비하며 남긴 노트를 발행해보고 있습니당
꼬리 재귀에 관해 알아봅시당.

Tail call optimization (TCO)

def foo():  
    return bar()  

def bar():  
    pass  

꼬리 재귀(tail recursion)

꼬리 재귀 함수의 마지막 단계에서 자기 자신을 호출할 때 추가 연산 없이 바로 호출하는 경우를 의미한다. 꼬리 재귀는 일부 컴파일러에서 최적화를 통해 반복문처럼 처리되어 스택 오버플로우의 위험을 줄일 수 있다.

일반 재귀 함수

public class FactorialExample {  
    // Normal recursive function to calculate factorial  
    public static int factorial(int n) {  
        if (n == 0 || n == 1) {  
            return 1;  
        }  
        return n \* factorial(n - 1); // Not tail recursion because multiplication happens after the recursive call  
    }  

    public static void main(String\[\] args) {  
        System.out.println("Factorial (Normal Recursion): " + factorial(5)); // Output: 120  
    }  
}  

n * factorial(n - 1) 연산이 재귀 호출이 반환된 후에 수행함
→ 각 재귀 호출이 자식 호출이 완료될 때까지 기다려야 하기 때문에 이 형태는 꼬리 재귀가 아님!!

꼬리 재귀 함수

public class FactorialTailRecursionExample {  
    // Tail-recursive function to calculate factorial  
    public static int factorialTail(int n, int accumulator) {  
        if (n == 0 || n == 1) {  
            return accumulator;  
        }  
        return factorialTail(n - 1, n \* accumulator); // Tail recursion because the recursive call is the last operation  
    }  

    public static void main(String\[\] args) {  
        System.out.println("Factorial (Tail Recursion): " + factorialTail(5, 1)); // Output: 120  
    }  
}  

factorialTail(int n, int accumulator) 메서드에서는 재귀 호출 factorialTail(n - 1, n * accumulator)이 함수의 마지막 연산임.
→ 재귀 호출 후에 추가적인 연산이 없기 때문에 꼬리 재귀에 해당!

찾아 본 것들

파이썬은 TRO(Tail Recursion Optimization)를 지원하지 않는다. (참고)

자바도 기본적으로 TRO을 지원하지 않는다고 한다. (하지만 특정 JVM 최적화 버전은 지원할 수도 있다) (참고)

추가로 보면 좋을 TRO 관련 글: https://rebugs.tistory.com/168

면접 질문 예상해보기

재귀 함수를 사용할 때 스택 메모리 영역에 어떤 일이 발생하는지 설명해 주세요. 재귀 호출이 깊어질수록 스택 오버플로우가 발생할 가능성에 대해 어떻게 생각하나요?

재귀 함수 호출 시마다 새로운 스택 프레임이 생성되며, 호출이 끝날 때마다 스택 프레임이 해제됩니다. 재귀 깊이가 깊어질수록 스택 사용량이 증가하여, 스택 오버플로우(Stack Overflow)가 발생할 가능성이 있습니다.

꼬리 질문. 재귀 함수는 일반적으로 반복문보다 더 많은 메모리를 사용합니다. 이를 최적화할 수 있는 방법을 아시나요?

메모이제이션으로 중간 결과를 저장해 중복 계산을 피함으로써 메모리 사용을 줄일 수 있습니다.

또 꼬리 질문. 그래도 재귀 호출이 많아졌을 때 메모리가 부족할 수 있습니다. 이것을 해결할 수 있는 다른 방법을 아시나요?

꼬리 재귀(Tail Recursion) 최적화가 있습니다. 꼬리 재귀는 재귀 호출이 끝나기 전에 불필요한 스택 프레임을 제거하여 스택 사용을 줄입니다. 일부 컴파일러는 꼬리 재귀를 최적화하여 반복문처럼 처리하기도 한다고 알고 있습니다.