스칼라 번역- 꼬리재귀 (Tail Recursion)

작성일 | Edited on | In | 댓글:

이 포스팅은 [scala-exercises 번역 시리즈]로 scala-exercises 사이트의 스칼라 튜토리얼을 공부하며 번역한 문서 입니다.
scala-exercises 는 스칼라 창시자인 마틴 오더스키 강의의 강의자료입니다.
따라서 강의를 들으며 본 문서를 같이 보는것을 추천합니다.
의역이 많습니다. 오역 및 오타 등은 코멘트로 알려주세요 😄
원문 : [scala-exercises tail_recursion]

꼬리 재귀(Tail Recurstion)

재귀 함수 응용프로그램

두개의 재귀 메소드의 실행과정(evaluation step) 을 비교해 보겠습니다.
먼저 두 수의 최대공약수를 계산하는 gcd 메소드를 생각해봅시다.
다음의 gcd 는 유클리드 알고리즘을 사용해 구현되었습니다.

1
2
def gcd(a: Int, b: Int): Int =
  if (b == 0) a else gcd(b, a % b)

gcd(14, 21) 는 다음의 실행과정을 거칩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
gcd(14, 21)
if (21 == 0) 14 else gcd(21, 14 % 21)
if (false) 14 else gcd(21, 14 % 21)
gcd(21, 14 % 21)
gcd(21, 14)
if (14 == 0) 21 else gcd(14, 21 % 14)
if (false) 21 else gcd(14, 21 % 14)
gcd(14, 7)
gcd(7, 14 % 7)
gcd(7, 0)
if (0 == 0) 7 else gcd(0, 7 % 0)
if (true) 7 else gcd(0, 7 % 0)
7

factorial 을 생각해봅시다:

1
2
def factorial(n: Int): Int =
  if (n == 0) 1 else n * factorial(n - 1)

factorial(4)는 다음의 실행과정을 거칩니다.

1
2
3
4
5
6
7
8
factorial(4)
if (4 == 0) 1 else 4 * factorial(4 - 1)
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * factorial(1)))
4 * (3 * (2 * (1 * factorial(0)))
4 * (3 * (2 * (1 * 1)))
24

이 두 시퀀스는 뭐가 다른걸까요?
가장 중요한 차이점은 gcd 경우 시퀀스가 본질적으로 감소하며 변합니다.
(gcd(21, 14 % 21) 가 gcd(14, 7) 처럼 점점 줄어듭니다)
그렇게 gcd의 하나의 호출에서 다음 호출로 넘어가며 결국엔 종료됩니다.
그리고 그 중간단계들 에는 if then elses 같은 표현식이 있습니다.
어쨌든 항상 우리가 최초 호출한 모양인 gcd(a,b) 로 돌아옵니다.

반면에 factorial 에선, 하나의 요소를 매 단계마다 추가한다는 것을 알 수 있습니다.
(4 * factorial(3) 에서 4 * (3 * factorial(2))으로 3 * 요소가 추가 된 것 처럼요)
즉, 최종 값으로 줄어들 때 까지 표현식은 점점 커집니다.

꼬리 재귀(Tail Recursion)

재활용(rewriting) 규칙의 차이점은 컴퓨터의 실제 실행의 직접적인 변화로 이어질 수 있습니다(데이터를 다시 만들거나 하지 않고 재 활용 합니다)
사실, 마지막 동작으로 자신을 호출하는 재귀함수가 있는 경우 해당 스택 프레임을 재사용할 수 있습니다.
이것을 꼬리 재귀 라고 부릅니다.

그리고 이 트릭을 적용함으로써, 꼬리 재귀함수는 불변의 스택 영역에서 실행될 수 있습니다. 따라서 이건 단순히 반복적인 프로세스(iterative process)와는 다른 방법입니다.
꼬리 재귀함수는 루프의 함수형 이며 루프처럼 효율적으로 실행됩니다.

다시 살펴보면, gdc의 else 부분에서 gcd의 마지막 동작으로 자신을 호출한다는 것을 알 수 있습니다.
그리고 이것은 본질적으로 크기가 불변인 재활용 시퀀스(rewriting sequence)로 변환되며,
이는 컴퓨터에서 실제 실행 시 불변의 공간에서 실행할 수 있는 꼬리재귀 호출로 변환됩니다.

반면에, factorial 을 보면 factorial(n - 1)이 호출 된 후에도 여전히 작업이 있습니다.
다시말해서, 호출의 결과에 대해 n을 곱해야 한다는 걸 알 수 있습니다.
따라서 재귀호출은 꼬래 재귀호출이 아니라는게 단계가 진행 되어지며 호출이 감소하지 않는 것(오히려 늘어나는 것) 에서 분명해집니다.
최종 값을 계산하기 전 까지 실제 유지해야 하는 중간값들이 쌓여있는것을 볼 수 있습니다.
그러므로 factorial은 재귀 함수가 아닙니다.

factorial과 gdc는 단지 자기 자신을 호출하지만, 일반적으로 함수는 다른 함수를 호출할 수 있습니다.
꼬리재귀는 만약 함수의 마지막 동작으로 다른 함수를 호출하는 경우 스택프레임을 두 함수 모두에 재사용 할 수 있습니다.
이러한 호출을 꼬리 호출(tail calls) 이라고 합니다.

스칼라에서의 꼬리재귀

스칼라에서 현재 함수에 대한 직접 재귀 호출(directly recursive calls) 만 최적화됩니다.
@tailrec 어노테이션을 사용해 꼬리재귀함수로 만들 수 있습니다.

1
2
@tailrec
def gcd(a: Int, b: Int): Int = …

만약 @tailrec 어노테이션을 사용했지만 gcd가 꼬리재귀가 아닌경우 오류가 발생합니다.

  • (역자추가) JVM은 보안상의 이유로 꼬리재귀를 지원하지 않기 때문에
    스칼라에서의 꼬리재귀는 컴파일러가 스택 하나만 사용해 재귀호출을 할 수 있도록 지원하고 있습니다.
    때문에 직접 호출하는 재귀호출 만 최적화가 가능하며 간접적으로 재귀호출이 일어나는 경우는 최적화 하지 못합니다.[참고]

읽어주셔서 감사합니다. 혹 글에 오역/추가할 내용이 있다면 코멘트 남겨주세요!🙆