재귀와 공재귀

1. 재귀 (Recursion)란 무엇인가?

재귀는 어떤 문제를 해결할 때, 그 문제를 더 작은 동일한 문제로 나누어 해결하는 방식이다. 이때, 자신을 호출하는 방식으로 문제를 풀어나가며, 조건을 만족하면 더 이상 재귀를 하지 않고 결과를 반환한다.

재귀 함수는 보통 두 가지 주요 요소를 포함한다.

• 기저 조건(Base Case): 재귀를 멈추는 조건으로, 일반적으로 가장 작은 문제를 해결하는 형태다.
• 재귀 호출(Recursive Case): 더 작은 문제를 해결하기 위해 자기 자신을 다시 호출하는 부분이다.

아래 팩토리얼을 구하는 재귀 함수 예시를 보자. 팩토리얼은 n! = n * (n-1) * (n-2) * ... * 1로 정의되며, 이를 재귀적으로 계산할 수 있다.

fun factorial(n: Int): Int {
    if (n <= 1) return 1 // 종료 조건
    return n * factorial(n - 1) // 재귀 호출
}

 

2. 공재귀(Tail Recursion)란 무엇인가?

공재귀는 재귀 함수 호출이 함수의 마지막 작업(혹은 반환값을 바로 리턴하는)일 때 발생하는 특수한 형태의 재귀다. 공재귀는 보통 더 효율적인 방식으로 동작하는데, 이는 컴파일러가 스택 프레임을 최적화할 수 있기 때문이다. 즉, 공재귀 함수는 일반적인 재귀 함수보다 더 적은 메모리를 사용하며, 스택 오버플로우를 피할 수 있다.

상기 팩토리얼을 구하는 재귀 함수를 공재귀 함수로 변환해보자.

tailrec fun factorialTailRec(n: Int, accumulator: Int = 1): Int {
    if (n <= 1) return accumulator // 종료 조건
    return factorialTailRec(n - 1, accumulator * n) // 재귀 호출
}

 

재귀와 공재귀는 둘 다 함수가 자기 자신을 호출하는 방식이지만, 메모리 사용과 성능에서 차이가 있다.

구현	함수가 자기 자신을 호출하며 계산	함수의 마지막 작업이 자기 자신을 호출
메모리 사용	각 호출마다 새로운 스택 프레임을 생성	호출이 종료될 때마다 스택 프레임을 재사용
효율성	많은 스택 메모리를 소모할 수 있음	최적화되어 스택 오버플로우를 방지
예시	factorial(n)	factorialTailRec(n, accumulator)

3. 재귀와 공재귀 중 선택하여 구현하는 방법

어떤 경우에는 재귀가 적합하고, 또 어떤 경우에는 공재귀가 적합할 수 있다. 선택은 주로 성능과 메모리 효율성에 따라 달라진다.

 

재귀를 선택할 때

• 문제의 크기가 작거나 중간 정도일 때
• 종료 조건이 간단하고 직관적인 경우
• 재귀 호출이 적당히 깊고, 스택 오버플로우가 발생할 가능성이 낮을 때

공재귀를 선택할 때

• 문제의 크기가 매우 클 때, 즉 깊은 재귀가 필요할 때
• 재귀 호출이 계속 반복되어도 성능에 영향을 미치지 않도록 최적화가 필요할 때
• 코틀린에서 tailrec 최적화가 가능한 경우

4. tailrec 최적화 사용

tailrec 키워드는 코틀린에서 공재귀(Tail Recursion)를 최적화하기 위해 사용되는 키워드다. 이 키워드를 사용하면 코틀린 컴파일러가 재귀 호출을 반복문처럼 처리할 수 있게 하여, 재귀 호출이 스택을 소모하지 않도록 최적화한다. 이렇게 하면 메모리 효율성을 크게 개선하고, 스택 오버플로우를 방지할 수 있다.

tailrec의 특징은 아래와 같다.

1. 메모리 효율성: 일반적인 재귀 함수는 각 호출마다 새로운 스택 프레임을 생성하여 메모리를 많이 소모한다. 반면, 공재귀는 재귀 호출을 반복문처럼 처리하므로 스택 프레임을 재사용할 수 있어, 메모리 소모를 줄이고 스택 오버플로우를 방지할 수 있다.
2. 성능 향상: tailrec 최적화가 적용되면, 호출이 깊어져도 성능에 영향을 미치지 않게 된다. 일반적인 재귀에서 발생할 수 있는 성능 문제를 해결할 수 있다.

tailrec 사용 조건

1. 마지막 작업이어야 한다: 함수에서 재귀 호출이 마지막 작업이어야만 tailrec 최적화가 가능하다. 즉, 재귀 호출 뒤에 다른 작업(예: 추가 계산, 다른 함수 호출)이 있으면 공재귀로 최적화되지 않는다.
2. 리턴값이 필요하다: 공재귀 함수는 종료 조건을 만족할 때 return을 통해 결과값을 반환해야 하며, 그 반환값이 바로 재귀 호출의 결과이어야 한다.
3. 함수 내에서 반환할 때 상태를 그대로 넘겨주어야 한다: 보통 공재귀에서는 accumulator와 같은 추가적인 상태를 넘겨주며 계산을 진행한다. 이 상태를 계속 넘겨주어야 최적화가 가능하다.

tailrec fun sumTailRec(n: Int, accumulator: Int = 0): Int {
    if (n <= 0) return accumulator
    return sumTailRec(n - 1, accumulator + n)
}