쿠...sal: [컴] tail-recursion 이 뭘까?

tail-recursion / 테일 리커젼 / 꼬리 반복

tail-recursion 이 무엇인지 알아보자.

tail-recursion

tail call

tail-recursion 을 이야기 하기 전에 tail call 이 뭔지 알면 좋다. tail call 은 함수의 return 부분에서 함수를 call 하는 것이다.

하지만 조건은 이 함수가 호출되고 난 이후에 아무런 추가연산을 하지 않는 것이다. 예를 들면, 아래 구조에서 func1 에서 return 부분에 sum(a, 3) 을 호출한다. sum(a,3) 은 return 하고 func1 에 돌아와서 return 값을 가지고 추가로 연산을 할 것이 없다. 바로 return 이 되면 된다. 이것이 tail call 이다.

def func1(a):
  return sum(a, 3)

def sum(a1, a2):
  return a1 + a2

반대로 아래 코드처럼 return 이후에 다시 연산을 해야 한다면 이것은 tail call 이 아닌 것이다.

def func1(a):
  return sum(a, 3) + 1

def sum(a1, a2):
  return a1 + a2

tail-recursion vs recursion

tail-recursion 은 이런 tail call 을 이용한 recursion(재귀) 이다.

이녀석이 우리가 흔히 사용하는 recursion 과 어떤 차이점이 있는지는 아래 글에서 잘 설명해 주고 있다. 아래글의 내용을 다시 정리해서 얘기해 보자.

What is tail-recursion?, StackOverflow

기존의 recursion 은 recursive 함수가 return 된 후에 계산을 한다. 그래서 호출한 recursive 함수가 모두 끝나기 전까지는 계산된 결과를 알 수가 없다.

def recursive(x):
    if x == 0 :
        return 0
    return recursive(x-1) + x

tail-recursion 에서는 계산을 먼저 진행한다. 그리고 나서 recursion 함수를 호출한다. 그래서 현재 step 의 결과를 다음 recursion 함수에 parameter로 함께 넘겨준다. 이렇게 하므로써 return 이후의 연산을 없애는 것이다.

def recursive_tail(x, result=0):
    if x == 0:
        return result
    return recursive_tail(x-1, result + x)

이런 식으로 programming 이 되면, return 에 recursive 함수의 호출만 남게 된다. 즉, 현재함수에서의 stack frame 이 필요없다는 이야기가 된다.

왜냐하면 그냥 함수에서 오는 값을 return 해주기만 하면 되기 때문이다. 연산을 해야하는 경우라면, 이전의 stack frame 을 가지고 있어야, 그 함수에 있던 local variable 을 사용할 수 있기 때문이다.

그래서 현재 쓰고 있던 stack frame 을 그냥 없애버리고, 다시 recursive 함수 호출에 stack frame 으로 사용할 수 있게 되기 때문에, 훨씬 stack frame 을 효율적으로 사용할 수 있어서 stack overflow 같은 경우가 생기지 않게 할 수 있다.

tail-recursion optimization languages

이렇기 때문에 compiler 가 최적화시키기도 좋다. 그렇다면 어떤 언어에서 tail-recursion 에 대한 최적화(optimization) 을 제공하는 지 알아보자. 아래 글을 참고하자.

Which languages support tail recursion optimization? [closed], StackOverflow

python

그런데 일단 python 에서는 Tail recursion 을 제거했다고 한다. 그렇기 때문에 위에 있는 python 예제는 좋은 예제는 아니다. python 에서 Tail recursion 을 제거한 것에 대한 얘기는 아래 블로그에서 잘 해주고 있다.

WEDNESDAY, APRIL 22, 2009 Tail Recursion Elimination

블로그에서 주장하는 바는 여러가지가 있지만, 가장 명쾌한 해답은 굳이 python 에서 Tail Recursion Elimination(TRE) 을 했는데, 굳이 가져다 쓰는 것은 좋은 방법이 아니다.라는 것이다. stack 을 tracing 하기 어렵다는 등의 여러가지 이유가 있으니 블로그 글을 읽어보자.

그리고 아래는 decorator 를 이용해서 python 에서 Tail-recursion 을 구현하는 방법이다.

Tail Call Optimization Decorator (Python recipe)

쿠...sal

[컴] tail-recursion 이 뭘까?

tail-recursion

tail call

tail-recursion vs recursion

tail-recursion optimization languages

python

See Also

댓글 없음:

댓글 쓰기