Tail Recursion 추가 포스팅

Scala는 Functional 스타일을 권장해서 Loop 보다는 Recursion을 더 권장한다. Loop보다 Recursion이 사람의 사고에 더 가깝다고 하고, 모든 Loop는 재귀로 표현할 수 있다고 한다. 처음에 교수님께서 과제 조건으로 for문이나 while문을 사용하지 말라고 하셔서 잘 이해가 안갔는데 이제야 이해가 된다.

 

 

 

아래 내용은 Scala By example의 4.6 Tail Recursion 부분에 나온 예제이다.

 

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

 

한줄로 끝나서 조금 허무하지만 엄청난 코드이다. 최대공약수를 구하는 코드를 tail recursion으로 작성한 것이다. 나 역시 그냥 recursion이랑 tail recursion을 막상 헷갈려해서 이를 비교해주는 코드도 보도록 하자. 아래는 팩토리얼을 구해주는 함수이다.

 

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

 

함수가 호출되면 stack이 push 되는데, factorial의 경우는 최초에 호출된 함수가 끝나지 않은 상태에서 계속 재귀가 되기 때문에 push가 연속해서 이루어지고, 재귀의 마지막까지 가면 그제서야 pop이 되면서 stack에 차지한 공간을 제거한다. 따라서 많은 재귀호출이 일어날 경우 stack over flow가 일어나게 된다. 

 반면에 gcd는 함수 내에서 재귀의 결과를 이용하는 것이 아닌, 현재의 함수는 종료되고, 새로운 함수를 호출하는 구조이기 때문에 push와 pop이 교대로 일어나기 때문에 차지하는 stack의 공간이 일정 공간 이상은 필요하지 않게 된다. 

 

 

위에 단순 recursion으로 작성했던 factorial을 tail recursion으로 작성해보자.

def factorial(n:Int, acc:Int = 1):Int = {
    if(n==0) acc*1 
    else factorial(n-1,acc*n) }