[알고리즘] 재귀 함수, 꼬리 재귀

재귀 함수

재귀 함수는 어떠한 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식의 함수이다.

반복문을 사용하는 함수를 재귀 함수를 통해 구현하는 것이 가능하다.

재귀 함수는 보통 재귀적 사용이 자연스러울 때 사용된다.

재귀 함수의 장점

• 코드가 간결해지고, 가독성이 좋아진다.
• 변수 선언을 줄일 수 있다.

재귀 함수의 단점

• 시간 복잡도의 계산이 반복문에 비해 어렵다.
• 함수 호출이 많아지면 Stack Overflow의 위험이 있다.
• 호출할 때마다 메모리의 스택이 쌓여 성능에 문제가 생긴다.

재귀 함수의 예제

public static int factorial(int n) {
    if(n == 1) return 1;
    return n * factorial(n - 1);
}

꼬리 재귀 알고리즘

재귀 함수의 단점을 보안하기 위한 최적화 방법이 꼬리 재귀 알고리즘이다.

일반 재귀 함수는 추가 연산이 존재하지만, 꼬리 재귀는 재귀 호출이 끝나고 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 것이다.

 

꼬리 재귀를 이용하면 함수 호출이 반복될 때 스택이 깊어지는 문제를 컴파일러가 선형으로 처리하도록 알고리즘을 바꾸기 때문에 스택을 재사용할 수 있다.

 

하지만 컴파일러가 꼬리 재귀 최적화를 지원하지 않는다면 일반 재귀처럼 돌아간다.

꼬리 재귀 예제

재귀의 예제로 썼던 팩토리얼을 보겠다.

public static int factorial(int n, int acc) {
    if(n == 1) return acc;
    return factorial(n-1, n * acc);
}