Tail Recursion(꼬리 재귀)란?

재귀함수 사용시 주의점

재귀함수를 공부할때 항상 나오는 단점이 "stack memory" 가 많이 필요하다는 말이다.

재귀함수란 A함수 안에서 A함수를 다시 부르는건데,

A함수가 종료되지 않은 상태에서 A함수를 한번더 부르기 때문에, 종료되지 않은 함수들이 계속해서 stack에 쌓여간다.

따라서 재귀호출이 너무 많이되면 stack memory가 overflow 될 수 있다.

이렇게 stack memory를 과다사용하는 재귀호출의 문제점을 피하기 위한 방법이 바로 Tail Recursion(꼬리재귀)이다.

 

Tail Recursion(꼬리 재귀)란?

아래 예를 보자 (1~n 까지의 합을 구하는 일반적인 재귀함수다)

r_sum 이라는 함수 내부에서 자기자신(r_sum)을 호출한다.

"r + r_sum()" 으로 되어 있기 때문에 r_sum(n-1) 함수가 종료되기 전까지 r_sum(n) 함수도 종료되지 않는다.

따라서 재귀함수의 마지막이 종료되기 전까지 모든 함수들이 종료되지 않고 stack memory에 쌓여있는 상태다.

def r_sum(n):
    if n==1:
        return 1
    else:
        return n+r_sum(n-1)

print(r_sum(10))

아래는 Tail Recursion(꼬리 재귀) 방식으로 수정한 함수이다.

tr_sum함수 내부에서 자기자신(tr_sum)을 호출하는건 동일하지만, 차이점은 tr_sum(n) 함수가 종료되면서, tr_sum(n-1) 바로 호출된다.

근데, 좀더 생각을 해보면 "tr_sum(n)이 종료되는건 아니기 때문데 stack에 쌓이는건 똑같지 않을까?" 하고 생각할 수도 있다.

이를 해결해 주는것이 바로 TCO (Tail Call Optimization) 이다.

실행시 컴파일러에서 코드 최적화를 해주는데, 이를 통해 우리가 원하던 방식으로(stack memory 에 쌓이지 않는) 코드 최적화를 해준다.

def tr_sum(n, total=0):
    if n==0:
        return total
    else:
        return tr_sum(n-1, total+n)

print(tr_sum(10))