Review: Evaluating a Function Application
f(e1, ..., en) 이라는 함수가 있다고 가정할 때, expression e1,...,en 의 결과 값은 v1,...,vn이 되며, 함수 f 안에 있는 e1,...,en을 v1,...,vn으로 교체해도 함수 f의 동작이 무방할 때 이를 substitution model이라고 한다.
아래 코드는 위의 글을 프로그램적으로 다시 쓴 것이다.
def f(x1,...,xn) = B; ...f(v1,...,vn)
def f(x1,...,xn) = B; ... [v1/x1,..., vn/xn]B
여기서 [v1/x1,...,vn/xn]B이 의미하는 것은 expression B에 있는 모든 vi는 xi에 의해 교체될 수 있음을 의미하고, [v1/x1,...,vn/xn]을 substitution이라고 부른다.
이번에는 아래의 유클리드 알고리즘을 사용하여 gcd를 구하는 것을 살펴보자.
def gcd(a: Int, b: Int): Int =
if (b==0) a else gcd(b, a%b)
gcd(14, 21)을 실행하면 아래와 같은 계산 과정을 거칠 것이다.
gcd(14, 21)
-> if (21 == 0) 14 else gcd(21, 14 % 21)
-> gcd(21, 14)
-> if (14 == 0) 21 else gcd(14, 21 % 14)
-> gcd(14, 7)
-> if ( 7 == 0) 14 else gcd(7, 14 % 7)
-> gcd(7, 0)
-> if ( 0 == 0) 7 else gcd(0, 7 % 0)
-> 7
이번엔 다른 경우를 살펴 보자.
def factorial(n: Int): Int =
if (n == 0) 1 else n * factorial(n-1)
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(x,y) 형태의 계산만을 사용해서 재귀를 호출해서 stack이 점점 늘어나지 않는데 반해 두번째 계산에서는 재귀를 진행할 수록 이전 계산 결과를 들고 다음 재귀를 호출하기 때문에 stack의 깊이가 점점 깊어지는 것을 알 수가 있다.
TailCall vs Tail Recursion
위에서 잠깐 stack이라는 것을 언급했는데 일단 함수 내에서 또 다른 함수를 호출하게 되면 원래 함수의 정보를 stack에 추가해서 저장을 해야 한다. factorial(4)를 보게 되면 stack이 4번 추가로 저장된 것을 알 수가 있다. 파라미터가 4라서 실행이 될 뿐 만약 더 큰 수의 값이 입력된다면 자칫하면 프로그램이 죽을 수도 있는 문제이다.
그럼 이번에는 피보나치 단계를 살펴보자.. 이것도 똑같은 재귀이고 함수 호출도 똑같은데 왜 stack이 늘어나지 않는 걸까?
factorial과의 차이를 살펴보자면 factorial은 리턴된 후 *의 연산과정이 있기 때문에 다시 돌아올 정보가 필요한 것이었다. 하지만 피보나치 같은 경우에는 그냥 결과 return만 시켜주기 때문에 추가로 stack에 저장할 필요가 없는 것이다.
이렇게 함수 호출 한 후 아무런 후속 작업도 취하지 않기 위해 함수 끝부분에서 다른 함수를 호출하는 것을 TailCall이라고 부른다. 그리고 함수 끝부분에서 호출하는게 자기 자신일 경우에 Tail Recursion이라고 부른다.
Tail Recursion in Scala
스칼라에서는 @tailrec라는 annotation을 통해 tail-recursion을 실행할 수가 있다.
@tailrec
def gcd(a: Int, b: Int): Int = ...
