Performance Degradation in Recursion
OCaml에서는 loop 대신 Recursion을 사용한다.
OCaml에서 loop를 지원하지만, 함수형 언어에서는 대체적으로 Recursion이 사용된다.
Recursion으로 loop를 완벽히 대체할 수 있으므로, Recursion을 사용하는 것을 권장한다.
프로그램의 함수 호출은 Call Stack을 통해 관리되는데, Call Stack은 메모리에 저장되므로 recursion을 통해 함수를 여러 번 호출할수록 Call Stack에 저장되는 정보가 많아진다.
즉, Recursion을 지나치게 많이 수행하면 Call Stack의 크기가 계속 커져
Stack Overflow가 발생할 수 있다.
Tail call optimization
함수형 언어에서는 C와 같은 언어와 달리 개발자의 최적화 요소가 적지만,
대신 컴파일러가 적극적으로 최적화를 수행한다.
특히 함수형 언어의 특징인 immutability로 인해 다양한 방법의 최적화가 가능하다.
What is Tail Call Optimization?
Tail Call Optimization은 함수 호출 중에 발생하는 오버헤드를 줄이기 위해, 함수 호출의 맨 마지막에서 발생하는 호출을 최적화하는 기술이다.
예를 들어, 1부터 인자로 주어진 정수까지의 합을 구하는 다음 함수를 보자.
example func)
let rec sum (n : int) : int =
match n with
| 0 -> 0
| x when x < 0 -> failwith "negative number"
(* 수행할 연산이 남아 sum (n - 1)이 반환될 때까지 Call Stack에서 대기 *)
| _ -> n + sum (n - 1) 만약 sum 5 를 실행하게 되면, Call Stack에 다음과 같이 함수 호출에 대한 정보가 저장된다.
call sum 0 <- top
call sum 1
call sum 2
call sum 3
call sum 4
call sum 5이와 같이 call stack의 크기가 점점 커지므로, stack overflow의 리스크를 가지고 있다.
따라서, Tail call optimization을 통해 다음과 같이 함수를 정의할 수 있다 :
example func)
let rec sum (n : int) (acc : int) : int =
match n with
| 0 -> acc
| x when x < 0 -> failwith "rejected"
| _ -> sum (n - 1) (acc + n)Tail call optimization을 사용해 코드를 작성하게 되면,
재귀 호출이 함수의 마지막 연산으로 수행되어 Call stack을 최적화할 수 있다.
위 함수에서 sum 5 0 을 실행하게 되면 Call stack에 다음과 같이 함수 호출에 대한 정보가 저장된다.
sum 5 0 호출 시
call sum 5 0 <- top
첫 번째 재귀 함수 호출 시
call sum 4 5 <- top (* sum 5 0 에 대한 스택은 pop *)
두 번째 재귀 함수 호출 시
call sum 3 9 <- top (* sum 4 5 에 대한 스택은 pop *)
...
마지막 재귀 함수 호출 시
call sum 0 15 <- top (* sum 1 14 에 대한 스택은 pop *)이처럼 Tail Call Optimization을 이용해 코드를 작성하면,
Call Stack에 쌓이는 메모리 공간이 최적화된다.
Transform Recursion to Tail Call Optimiziation
Recursion 함수를 Tail Call Optimization으로 변환하는 대표적인 방법은 다음 2가지이다.
- 누산기(accumulator) 활용
Recursive 함수가 추가적인 accumulator 인자를 받도록 수정하고,
계산 결과를 누산기에 누적하여 인자로 전달하도록 하는 방법이다.
Recursive가 끝나는 Base Case에서 누산된 결과를 반환하도록 작성하면 된다.
example - Recursive Function)
let rec sum (n : int) : int =
match n with
| 0 -> 0
| x when x < 0 -> failwith "negative number"
| _ -> n + sum (n - 1)
example - Tail Call Optimization with accumulator variable)
let rec sum (acc : int) (n : int) : int = (* accumulator variable 추가 *)
match n with
| 0 -> acc (* Base Case에서 누산된 결과 반환 *)
| x when x < 0 -> failwith "rejected" (* 예외 처리 *)
| _ -> sum (acc + n) (n - 1) (* TCO 적용 - Recursion이 함수의 마지막 연산임 *)
- 함수 내부의 로컬 함수 정의
함수 내부에 로컬 함수를 정의해 Tail Call Optimization을 수행할 수도 있다.
이 방법은 함수 타입을 유지할 수 있기 때문에 해당 함수를 호출하는 다른 부분들을 수정할 필요가 없다.
example - Recursive Function)
let rec sum (n : int) : int =
match n with
| 0 -> 0
| x when x < 0 -> failwith "negative number"
| _ -> n + sum (n - 1)
example - Tail Call Optimization with inner function)
let sum (n : int) : int =
let sum_helper (acc : int) (n : int) : int = (* inner function 정의 *)
begin
match n with
| 0 -> acc
| x when x < 0 -> failwith "negative number"
| _ -> sum_helper (acc + n) (n - 1)
end
sum_helper 0 n (* inner function 호출 *)