282
2
부
기본기 다지기
8
:
40320
9
:
362880
10
:
3628800
[
success
]
Total time
:
0 s
,
completed Feb 12
,
2014 6
:
12
:
18 PM
다음은 이를 재귀적으로 구현해본 첫 번째 코드다.
//
src
/
main
/
scala
/
progscala2
/
fp
/
recursion
/
factorial
-
recur1
.
sc
import scala
.
annotation
.
tailrec
//
아래
애노테이션에서
//
를
없애면
무슨
일이
벌어질까
?
//
@
tailrec
def factorial
(
i
:
BigInt
):
BigInt
=
{
if
(
i
==
1
)
i
else i
*
factorial
(
i
-
1
)
}
for
(
i
<
-
1 to 10
)
println
(
s
"$
i
:\
t
${
factorial
(
i
)}")
출력은 같지만, 지금은 변경 가능한 변수가 없다 (함수를 테스트하기 위한 마지막
for
내장의
i
가 변경 가능한 것이 아닌가 생각할 수도 있지만, 그렇지 않다. 이에 대해서는
7
장에서 살펴볼
것이다 ). 재귀는 또한 일부 함수를 기술하는 가장 자연스러운 방법이기도 하다.
하지만 재귀 사용에는 두 가지 단점이 있다. 하나는 반복된 함수 호출로 인한 성능상의 부가 비
용이고, 다른 하나는 스택 넘침
stack
overflow
의 위험성이다.
우리가 순수 함수형을 사용해서 재귀적으로 구현하고, 컴파일러나 실행 환경이 이를 루프로 최
적화해준다면 멋질 것이다. 이제 그런 방법에 대해 살펴보자.
6.4
꼬리 호출과 꼬리 호출 최적화
어떤 함수가 자기 자신을 호출하되, 그 호출이 해당 함수의 마지막 (즉, ‘꼬리’ ) 연산인 경우를
일컬어 꼬리 호출
tail
call
재귀라고 한다. 꼬리 호출 재귀는 매우 중요하다. 왜냐하면 루프로 가장
283
6
장
스칼라 함수형 프로그래밍
쉽게 변환할 수 있는 재귀 호출 유형이기 때문이다. 루프를 사용하면 스택 넘침의 가능성이 없
어지며, 재귀적 함수 호출에 따른 부가 비용도 사라진다. 아직
JVM
자체에서는 꼬리 호출 재귀
의 최적화를 지원하지 않지만,
scalac
는 이를 최적화하려 시도한다.
하지만 우리가 본 계승 예제는 꼬리 재귀가 아니다. 왜냐하면
factorial
이 자기 자신을 호출한
다음, 그 결과에 대해 곱셈을 수행하기 때문이다.
2
장에서 스칼라에
@
tailrec
(
http
://
bit
.
ly
/
1wl47Y9
)이라는 애노테이션이 있다는 것을 얘기했다. 기억하는가! 그 애노테이션을 여러분이
꼬리 호출 재귀라고 생각하는 함수에 추가할 수 있다. 컴파일러가 그 함수를 최적화할 수 없다면
예외를 던질 것이다.
앞의 예제에서
@
tailrec
앞에 있는
//
를 없애면 무슨 일이 벌어지나 보라.
다행히
factorial
에 대한 꼬리 재귀 구현도 존재한다. 그에 대해서는
2
.
5
.
4
절 ‘내포된 메서드
정의와 재귀’에서 살펴봤다. 다음은 그때 본 구현을 정리한 것이다.
//
src
/
main
/
scala
/
progscala2
/
fp
/
recursion
/
factorial
-
recur2
.
sc
import scala
.
annotation
.
tailrec
def factorial
(
i
:
BigInt
):
BigInt
=
{
@
tailrec
def fact
(
i
:
BigInt
,
accumulator
:
BigInt
):
BigInt
=
if
(
i
==
1
)
accumulator
else fact
(
i
-
1
,
i
*
accumulator
)
fact
(
i
,
1
)
}
for
(
i
<
-
1 to 10
)
println
(
s
"$
i
:\
t
${
factorial
(
i
)}")
이 스크립트도 이전 예제와 같은 결과를 만들어낸다. 이제
factorial
은 모든 작업을 내포 메
서드
fact
를 통해 수행한다.
fact
는 진행 중인 계산을
accumulator
인자로 넘기기 때문에 꼬
리 재귀다. 꼬리 위치에 있는 재귀 호출이 이루어지기 전에 곱셈을 통해 이 인자를 계산한다. 이
제
@
tailrec
애노테이션이 더 이상 컴파일 오류를 내지 않는다. 컴파일러가 재귀를 루프로 성
공적으로 바꿀 수 있기 때문이다.
284
2
부
기본기 다지기
factorial
의 원래의 비꼬리
non
-
tail
재귀 구현을 큰 수 (예를 들면
10
,
000
)를 인자로 넣어서 호
출해보면, 일반적인 데스크톱 컴퓨터에서는 스택 넘침이 발생한다. 하지만 꼬리 재귀를 사용한
구현은 성공적으로 작동하고, 아주 큰 수를 반환한다.
이런 식으로 값을 누적시키기 위한 인자를 추가한 꼬리 재귀 함수를 내포시켜서 사용하는 관용
적인 구문은 여러 재귀 알고리즘을 꼬리 재귀로 변환할 때 매우 유용하다.
CAUTION
_
어떤 재귀 호출 메서드가 파생 타입에 의해 오버라이딩될 수 있는 경우 꼬리 호출 최적화를 적
용할 수 없다. 따라서 재귀 메서드는 반드시
private
나
final
키워드와 함께 정의하거나 다른 메서드에 내
포시켜야 한다.
6.4.1
꼬리 호출 트램펄린
트램펄린
trampoline
은 여러 함수가 한 번에 하나씩 다른 함수를 호출하면서 이루어지는 루프를
말한다. 마치 트램펄린처럼 여러 함수가 서로 호출을 주고받기 때문에 이런 이름이 붙었다.
어떤 함수
A
가 자기 자신을 호출하지는 않지만, 다른 함수
B
를 호출하고,
B
는 다시
A
를 호출하
고,
A
는 다시
B
를 호출하는 식의 재귀를 고려해보자. 이런 식으로 주고받는 재귀를 트램펄린을
사용해서 루프로 변환할 수 있다. 트램펄린은 재귀적인 함수 호출 없이도 주고받는 계산을 쉽게
수행할 수 있게 도와주는 데이터 구조다.
스칼라 라이브러리에는 이런 목적의
TailCalls
(
http
://
bit
.
ly
/
1q95Jyn
) 객체가 있다.
다음 코드는 어떤 수가 짝수인지 약간 비효율적으로 결정한다 (
isEven
과
isOdd
가 서로를 참조
하기 때문에, 이 코드를 입력하려면
REPL
의
:
paste
를 사용해야 한다 ).
//
src
/
main
/
scala
/
progscala2
/
fp
/
recursion
/
trampoline
.
sc
//
출처
:
scala
-
lang
.
org
/
api
/
current
/
index
.
html
#
scala
.
util
.
control
.
TailCalls
$
import scala
.
util
.
control
.
TailCalls
.
_
def isEven
(
xs
:
List
[
Int
]):
TailRec
[
Boolean
]
=
if
(
xs
.
isEmpty
)
done
(
true
)
else tailcall
(
isOdd
(
xs
.
tail
))
def isOdd
(
xs
:
List
[
Int
]):
TailRec
[
Boolean
]
=
if
(
xs
.
isEmpty
)
done
(
false
)
else tailcall
(
isEven
(
xs
.
tail
))
Get 프로그래밍 스칼라: 실용적인 스칼라 활용법을 익히는 가장 확실한 실전 바이블 (2.11.x 버전 기반) now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
