Scala를 만든 Martin Odersky가 만든 Scala By Example라는 문서가 있습니다.(현재 문서는 DRAFT상태로 2010년 7월 13일 업데이트버전이네요.) 재귀에는 Tail Recursion이라는 것이 있는데 그동안 감을 좀 못잡고 있다가 지난주에 공부한 내용을 정리해 봅니다.
아래 내용은 Scala By Example의 4.6 Tail Recursion 부분에 나온 예제입니다.
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
////////////////////////////////////////////////////////////////////////////////////////
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)
→→ gcd(14, 21 % 14)
→ gcd(14, 7)
→ if (7 == 0) 14 else gcd(7, 14 % 7)
→→ 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(5)
→ if (5 == 0) 1 else 5 * factorial(5 - 1)
→ 5 * factorial(5-1)
→ 5 * factorial(4)
→...→ 5 * (4 * factorial(3))
→...→ 5 * (4 * (3 * factorial(2)))
→...→ 5 * (4 * (3 * (2 * factorial(1))))
→...→ 5 * (4 * (3 * (2 * (1 * factorial(0))))
→...→ 5 * (4 * (3 * (2 * (1 * 1))))
→...→ 120
gcd예제는 Tail Recursion이고 factorial 예제는 Tail Recursion이 아닙니다. 함수가 호출되면 stack에 push가 되는데 factorial의 경우는 최초에 호출된 함수가 끝나지 않은 상태에서 계속 재귀가 되기 때문에 push가 연속해서 이루어지고 재귀의 마지막까지 가면 그제서야 pop이 되면서 stack에 차지한 공간을 제거합니다. 때문에 많은 재귀호출이 일어날 경우 stack overflow가 일어날 가능성이 있습니다. 반면에 gcd는 함수내에서 재귀의 결과를 이용하는 것이 아닌 현재의 함수는 종료되고 새로운 함수를 호출하는 구조이기 때문에 push와 pop이 교대로 일어나기 때문에 차지하는 stack의 공간이 일정공간이상은 필요하지 않습니다. 당연히 구조상 Tail Recursion이 훨씬 좋은 구조입니다.(이 부분도 자연히 되는것은 아니고 Compiler의 도움이 필요하다고 합니다. 같은 방식으로 작성한다고 모든 언어가 Tail Recursion이 되는 것은 아닌것 같습니다.)
실제로 Tail Recursion인지 확인하는 방법은 Miracle군이 가르쳐준 예외를 던져보는 방식이 가장 명확한것 같습니다.
def factorial(n: Int): Int = if (n == 0) throw new Exception else n * factorial(n - 1)
factorial(5)
위의 코드의 Tail Recursion 여부를 확인하가 위해서 재귀호출의 종료부분에서 예외를 던지도록 처리했습니다. 그렇게 아래처럼 Tail Recursion이 되지 않고 재귀 호출이 계속 중첨되어서 실행되었음을 확인할 수 있습니다.
def factorial(n: Int, acc: Int = 1): Int = if (n == 0) throw new Exception else factorial(n- 1, acc * n)
factorial(5)
이번에는 코드를 Tail Recursion이 되도록 수정하였습니다.(실제 로직대로 수행되려면 throw new Exception 대신에 acc * 1 부분이 들어가야 합니다.) 코드를 돌려보면 아래와 같이 Tail Recursion이 되어서 예외가 한번만 던져지는 것을 확인할 수 있습니다.
Good job!
스터디때 나오거 울거먹기....
음냥...
gcd는 무슨 값을 구하는 함수인가요 ?
설마
21-14는 아니겠죠 ? ㅋㅋ
최대공약수 greatest common divisor인가 그럴걸? ㅎㅎㅎ
그러고 보니 21-14하면 7이네 ㅋㅋㅋ
스칼라 공부하는데, 좋은 정보 감사합니다.
블로그에 위의 내용 퍼가겠습니다.
http://blog.naver.com/pluulove84
옙! ㅎㅎ
안녕하세요 항상 좋은글 감사히 읽고 있습니다.
많이 지난 포스트에 질문을 올리게 됐네요
저는 이번에 꼬리 재귀를 알게 되어 자바로 구현을 해보았는데요.
실제로 스택이 증가하는 것을 확인하였습니다.
스택오버플로우도 발생을 했구요..
구글 검색해보니, JVM의 보안 특성상 꼬리 재귀를 지원하지 않는다고 확인을 했습니다.
JVM 위에서 도는 함수형 언어역시 한계라고 하던데.(scala역시..)
이 포스트를 보고 아리송 해서요..
혹시 꼬리 재귀에 대해 jvm 특성이 있다던가 조금 더 정보가 있으신지요?
제가 검색한 관련 링크 첨부해봅니다.
http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations
예 JVM에서 꼬리재귀를 지원하지 않구요 그래서 스칼라는 스칼라 컴파일러가 꼬리재귀로 스택하나만 사용해서 재귀호출을 할 수 있도록 최적화를 해주고 있습니다. 물론 Scala는 JVM에서 동작하기 때문에 JVM의 한계에 영향을 받아서 꼬리재귀역시 제한적인 내에서만 사용할 수 있습니다. Programming in Scala의 8.9장에 해당 내용이 좀 나오는데요. 책에 나온대로라면 스칼라는 같은 함수내에서 자신을 직접 호출하는 재귀호출만 최적화 할 수 있고 간접적으로 재귀호출이 일어나는 경우에는 최적화 하지 못합니다.