3.2. Recursion - 3.2.2 Non-Tail Recursion

CS - 3. Common Algorithms - 3.2. Recursion - 3.2.2 Non-Tail Recursion

 

💡Tail recursion is when a function can directly return the result of a recursive call - there are no outstanding operations, and there is no need for the call stack frame to be preserved. So it can be translated to a “goto with arguments”, and the stack usage will be constant.

In “non-tail recursion”, there are outstanding operations after the recursive call, and the stack frame cannot be nuked.

 

꼬리 재귀는 함수가 재귀 호출의 결과를 직접 반환할 수 있는 경우로, 미결 연산이 없고 호출 스택 프레임을 보존할 필요가 없습니다. 따라서 " goto with arguments 로 번역할 수 있으며 스택 사용량은 일정합니다.
"비꼬리 재귀"에서는 재귀 호출 이후에 미결 연산이 존재하며 스택 프레임을 완전히 제거할 수 없습니다.

(cannot be nuked 를 완전히 제거할 수 없다고 해석했는데 확실하지 않다.)

 

비-꼬리 재귀(Non-Tail Recursion)는 재귀 함수에서 재귀 호출이 함수의 마지막 작업이 아닌 경우를 의미합니다. 

이 경우, 재귀 호출 후에 추가로 수행해야 하는 작업이 남아 있으므로, 시스템 스택에 이전 함수 호출의 정보를 계속 유지해야 합니다.

이를 이해하기 쉽게 설명하자면, 비-꼬리 재귀는 재귀 호출이 이루어진 후에도 다른 작업을 수행해야 하기 때문에, 재귀 호출이 끝난 후에 이전 상태로 돌아와야 합니다. 

따라서 스택에 이전 함수 호출의 정보를 보관해야 합니다.

 

In Python

파이썬에서 비-꼬리 재귀를 구현하는 예시는 저번에 작성했던 팩토리얼 계산입니다.

def factorial_nontail(n):
    if n == 1:
        return 1
    else:
        return n * factorial_nontail(n - 1)

여기서 꼬리 재귀로 구현하게 된다면

def factorial_tail(n, acc=1):
    if n == 1:
        return acc
    else:
        return factorial_tail(n-1, n*acc)

이런식으로 바꿀수 있습니다.

 

위의 factorial_nontail 함수에서 마지막줄 factorial_nontail(n-1)이 재귀 호출이며,

이 호출 후에 n * 연산이 수행되므로 비-꼬리 재귀입니다.

이러한 비-꼬리 재귀는 팩토리얼 계산 외에도

트리 구조의 탐색, DFS 등 다양한 알고리즘에 활용됩니다.

 

하지만 비-꼬리 재귀는 꼬리 재귀에 비해 스택오버플로우 위험이 높으므로, 재귀 깊이가 깊어질 경우를 조심해야합니다.

 

왜 비-꼬리 재귀가 꼬리 재귀에 비해서 스택오버플로우 위험이 높을까요?

 

앞에서 비-꼬리 재귀는 재귀 호출 이후에도 다른 작업을 수행해야 하기때문에, 재귀 호출이 끝난 후에 이전 상태로 돌아와야 한다고 했습니다. 

따라서 각 재귀 호출에 대한 정보를 스택에 계속 저장해야 합니다.

이렇게 되면 재귀 호출이 많아질수록 스택에 저장되는 정보의 양이 늘어나고, 이는 결국 스택 오버플로우를 초래할 수 있습니다.

반면에 꼬리 재귀에서는 재귀 호출이 함수의 마지막 작업이므로, 재귀 호출 후에 처리해야 할 작업이 없습니다. 

따라서 이전 재귀 호출에 대한 정보를 유지할 필요가 없어, 스택에 저장되는 정보의 양이 적어집니다. 

이러한 특성 때문에 꼬리 재귀는 비-꼬리 재귀에 비해 스택 오버플로우 위험이 적습니다.

 

(하지만 프로그래밍 언어에 따라 꼬리재귀 최적화를 지원하는것이 아니기 때문에 깊어지지 않도록 주의는 해야합니다. 파이썬도 꼬리재귀 최적화를 지원하지 않습니다.)