Outsider's Dev Story

Stay Hungry. Stay Foolish. Don't Be Satisfied.
RetroTech 팟캐스트 44BITS 팟캐스트

Scala의 Tail Recursion 간단 예제

Functional 스타일을 권장하는 Scala에서는 루프(Loop)보다는 재귀(Recursion)를 권장합니다. 보통 재귀가 사람의 사고의 더 가깝다고하고(루프에 너무 익숙해져서인지 아직은 잘 모르겠습니다.) 모든 Loop는 재귀로 표현할 수 있다고 합니다.(재귀로 하는 법을 연습중인데 잘 안되긴 하네요. ㅡㅡ;;)

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이 되지 않고 재귀 호출이 계속 중첨되어서 실행되었음을 확인할 수 있습니다.

factorial이 6번 나온 오류 스택 트레이스 화면


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이 되어서 예외가 한번만 던져지는 것을 확인할 수 있습니다.

factorial이 한번만 나온 오류 스택 트레이스 화면

2010/10/12 03:18 2010/10/12 03:18