재귀 함수와 꼬리 재귀

송윤재·2025년 2월 17일

📌재귀 함수란?

재귀 함수(Recursive Function)는 자기 자신을 호출하는 함수입니다. 특정 문제를 작은 단위로 쪼개어 같은 문제를 반복적으로 해결할 수 있도록 도와줍니다. 대표적인 예로 팩토리얼, 피보나치 수열, DFS(깊이 우선 탐색) 등이 있습니다.

재귀(Recursive) vs 반복(Iteration)

반복과 재귀의 가장 큰 차이는, 재귀는 스스로를 호출한다는 점에 있다.

반복문으로 구현한 팩토리얼

int factorial(int num){
  int result = 1;
  for(int i = 1 ; i <= num ; i++){
      result = result * i;
  }
  return result;
}

재귀로 구현한 팩토리얼

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

두 방식은 시간 복잡도와 코드의 양에서 상호교환적(Trade-off)인 측면을 보인다.
시간 복잡도의 측면에서 보면, 재귀 호출의 수는 클 것이고 반복을 쓰는 것이 좋을 수 있다. 하지만 코드의 길이를 중점으로 한다면, 재귀가 나을 수 있다.

재귀
재귀는 같은 함수를 호출하고 호출한다. 때문에 코드의 길이는 짧다. 그러나 분석을 해보면, 호출이 상당히 많아지면 시간 복잡도가 지수 단위(Exponential)로 증가할 수 있다.
그러므로, 재귀의 사용은 짧은 코드라는 점에서 이점이지만, 반복보다 높은 시간 복잡도를 가진다.
반복
코드 블록의 반복이다. 이것은 코드가 길어지게 되지만, 일반적으로 재귀보다 낮은 시간 복잡도를 가진다.

재귀 함수의 Call Stack 동작 과정

재귀 함수가 호출될 때마다 새로운 함수 호출 정보(매개변수, 지역 변수 등)가 Stack Frame에 저장됩니다.
이전 함수의 실행이 완료되지 않았으므로, 새로 호출된 함수의 결과가 반환된 후에도 기존 함수의 나머지 연산을 수행해야 하기 때문입니다.
즉, "새로운 함수가 실행된 후에도 기존 함수에서 진행해야 할 연산이 남아 있기 때문에" 기존 함수의 정보가 Stack 영역에 유지됩니다.

예를 들어, factorial(3)을 호출하면 Call Stack은 다음과 같이 동작합니다.

factorial(3) 호출 → Call Stack: [factorial(3)]
factorial(2) 호출 → Call Stack: [factorial(3), factorial(2)]
factorial(1) 호출 → Call Stack: [factorial(3), factorial(2), factorial(1)]
factorial(1) 반환 (1) → Call Stack: [factorial(3), factorial(2)]
factorial(2) 반환 (2 × 1 = 2) → Call Stack: [factorial(3)]
factorial(3) 반환 (3 × 2 = 6) → Call Stack: []

💡 기존 함수들이 Stack에 유지되었던 이유

factorial(3)는 factorial(2)의 결과를 받아야 하므로 factorial(2)가 끝날 때까지 Stack에서 제거되지 않음.
factorial(2)도 factorial(2)의 결과를 받아야 하므로 Stack에서 남아있음.
같은 방식으로 계속 유지됨.

즉, "스택에 저장된 기존 함수가 할 일을 남겨둔 상태이기 때문에, 새로운 함수가 실행되는 동안 기존 함수의 Stack Frame이 유지된다"는 것이 핵심

재귀 함수를 사용할 때는 콜스택 증가로 인한 메모리 낭비, Stack Overflow 발생 위험을 조심해야 한다.
이 때 재귀 함수를 꼬리 재귀 형태로 작성할 수 있다면 이 문제를 회피할 수도 있다.
C++, C#, Kotlin, Swift은 꼬리 호출 최적화(TCO: Tail-Call Optimization)를 지원하며, JavaScript는 ES6 스펙에서 지원한다고 한다.

📌꼬리 재귀(Tail Recursion)

꼬리 재귀(Tail Recursion)는 재귀 호출이 함수의 마지막 연산(반환값)으로 수행되는 경우를 의미합니다.
즉, 재귀 호출 이후에 추가적인 연산(예: +, * 등)이 존재하지 않는 형태입니다.

일반 재귀 vs 꼬리 재귀 비교

일반 재귀

public class FactorialRecursive {
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);  // 재귀 호출 후 추가적인 곱셈 연산이 존재!
    }

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 결과: 120
    }
}

재귀 호출 이후에 n * factorial(n-1) 연산이 남아 있음
Stack Frame이 계속 유지됨 (최적화 불가능)
깊이 n만큼 스택이 쌓이므로 Stack Overflow 위험 존재

꼬리 재귀

public class FactorialTailRecursive {
    public static int factorialTail(int n, int acc) {
        if (n == 1) {
            return acc;
        }
        return factorialTail(n - 1, acc * n); // 마지막에 재귀 호출만 수행!
    }

    public static int factorial(int n) {
        return factorialTail(n, 1); // 초기 값 설정
    }

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 결과: 120
    }
}

재귀 호출 이후에 추가 연산이 없음 (factorialTail(n-1, acc * n))
현재 함수의 Stack Frame을 유지할 필요 없음 (TCO 가능)
재귀가 반복문처럼 최적화될 수 있음

TCO (Tail Call Optimization, 꼬리 호출 최적화)

꼬리 재귀를 사용하면 일부 언어에서 TCO(Tail Call Optimization)을 통해 Stack Frame을 재사용하는 최적화를 수행할 수 있습니다.

💡TCO의 원리

일반적인 재귀 함수는 각 호출마다 새로운 Stack Frame을 생성
하지만 꼬리 재귀는 기존 함수의 연산이 끝났으므로 새로운 Stack Frame을 만들 필요가 없음
따라서 현재 Stack Frame을 재사용하여 메모리 사용을 줄일 수 있음

💡TCO 지원 여부

Java는 TCO를 기본적으로 지원하지 않음

JVM(Java Virtual Machine)은 Stack Trace 유지를 중요하게 여겨 기본적으로 TCO를 제공하지 않음
Scala는 기본적으로 JVM 위에서 동작하기 때문에 일반적으로는 TCO를 지원하지 않지만, 컴파일러가 특정한 꼬리 재귀를 반복문으로 변환해 최적화하는 기능을 제공(@tailrec 어노테이션)

출처

https://velog.io/write?id=853e7703-130b-4e9b-8c54-260c1e08c073
https://sayyeah.tistory.com/9
https://velog.io/@whjoon0225/%EC%9E%AC%EA%B7%80%EC%9D%98-%EC%B5%9C%EC%A0%81%ED%99%94-Optimization-of-Recursion