3.2. Recursion - 3.2.1 Tail Recursion

CS - 3. Common Algorithms - 3.2. Recursion - 3.2.1. Tail Recursion

 

 

3.2 Recursion

💡 Recursion is a method of solving problems where the solution depends on solutions to smaller instances of the same problem. A recursive algorithm must have a base case. A recursive algorithm calls itself, recursively.

 

재귀는 동일한 문제의 작은 인스턴스에 대한 해결책에 따라 해결책이 달라지는 문제를 해결하는 방법입니다. 재귀 알고리즘에는 기본 사례가 있어야 합니다. 재귀 알고리즘은 스스로를 재귀적으로 호출합니다.

 

 

3.2.1 Tail Recursion

💡 Tail recursion is a special kind of recursion where the recursive call is the very last thing in the function. It’s a function that does not do anything at all after recursing.

 

꼬리 재귀는 재귀 호출이 함수의 맨 마지막에 있는 특별한 종류의 재귀입니다. 재귀 이후에는 아무 작업도 수행하지 않는 함수입니다.

 

재귀 (Recursion) 입니다.재귀는 함수가 자신을 다시 호출하는 것을 의미합니다.일반적인 재귀에서는 함수가 자신을 호출하고, 그 결과를 이용해 계산을 수행합니다.

 

Tail Recursion 과 Non-Tail Recursion으로 크게 나눠볼수 있는데, Tail Recursion은 재귀 호출이 함수의 마지막 연산이 되는 경우를 말합니다.즉, 재귀 호출 결과를 가공하지 않고 그대로 반환합니다.

이런 특성 때문에 Tail Recursion은 반복문과 유사한 성질을 가집니다.

 

 

In Python

파이썬에서 tail recursion구현의 예시로 팩토리얼 계산 함수를 들어보겠습니다.

 

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

위의 함수는 일반적인 재귀를 통한 팩토리얼 계산입니다.

이를 Tail Recursion으로 바꾸려면, 추가적인 인자를 이용하여 이전까지의 계산 결과를 인자로 넘기는 방식을 사용합니다.

 

def factorial_tail(n, acc=1):  # 인자의 값에 = 로 설정해주면, 인자의 defautl 값은 = 로 설정해준 값 입니다.
    if n == 1:
        return acc
    else:
        return factorial_tail(n-1, n*acc)

acc라는 추가 인자를 이용해 이전까지의 게산 결과를 게속해서 넘기고 있습니다.

이렇게 하면 재귀 호출이 마지막 연산이 되므로 Tail Recursion이 됩니다.

 

 

Tail Recursion을 사용하는 이유는 크게 두가지 입니다.

 

1. 코드의 가독성 향상 

- Tail Recursion은 일반적인 재귀보다 코드가 간결해지는 경향이 있습니다.

 

2. 메모리 효율성

- 일반적인 재귀는 호출할 때마다 스택에 메모리를 쌓아가기 때문에, 호출 횟수가 많아지면 메모리를 많이 사용하게 됩니다.

반면 Tail Recursion은 컴파일러나 인터프리터가 최적화를 통해 반복문처럼 메모리를 적게 사용할 수 있습니다.

 

하지만 Python에서는 Tail Recursion의 호출 최적화를 지원하지 않기때문에 재귀를 너무 깊게 사용하지 않도록 해야합니다. ( appendix 에 추가설명)

 

 

 

Appendix (Recursion 과 memory)

 

재귀 호출이 발생하면, 각 호출마다 메모리에 스택 프레임이 새롭게 생성됩니다. 이 스택 프레임에는 함수의 매개변수, 지역 변수, 반환 주소 등이 저장됩니다.

따라서 재귀 호출이 깊어질수록 이러한 스택 프레임이 계속해서 쌓이게 되는데, 이렇게 스택 메모리가 계속 증가하다가 사용 가능한 스택 메모리를 모두 소진하면 '스택 오버플로우' 오류가 발생하게 됩니다.

 

일반적으로 꼬리 재귀(Tail Recursion)는 이러한 문제를 해결하는 방법 중 하나입니다.

함수의 재귀 호출이 마지막 연산이 되고, 그 결과를 그대로 반환하는 형태의 재귀를 꼬리 재귀라 합니다.

이러한 특성 덕분에, 테일 재귀를 지원하는 언어의 컴파일러나 인터프리터는 스택을 새로 생성하는 대신 기존의 스택을 재활용하는 최적화를 수행할 수 있습니다. 이를 '테일 호출 최적화(Tail Call Optimization)'라고 부르며, 이를 통해 스택 오버플로우를 방지할 수 있습니다.

 

하지만 Python은 이러한 테일 호출 최적화를 지원하지 않습니다. 이는 Python의 설계 철학 중 하나인 '읽기 쉬운 코드'에 부합하지 않기 때문입니다. 테일 호출 최적화를 사용하면, 오류가 발생했을 때 스택 트레이스가 실제 실행 흐름을 정확히 반영하지 않게 되어 디버깅이 어려워지기 때문입니다.

 

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

sum(4) # 10

 

이런 일반적 재귀 함수로 피보나치 수열을 구한다고 정의합니다.

 

위 함수는 

sum(4)
4 + sum(3)
4 + (3 + sum(2))
4 + (3 + (2 + sum(1)))
4 + (3 + (2 + (1 + sum(0))))
4 + (3 + (2 + (1 + 0)))
4 + (3 + (2 + 1))
4 + (3 + 3)
4 + 6
10

이러한 과정으로 연산이 되며 stack frame 

함수 내에서 두 번의 호출이 일어나서 2^n개의 stack fram이 쌓입니다.

 

반면 tail recursion으로 함수를 정의해 봅니다.

def sum_tail_recursion(n, acc):
    return acc if n == 0 else sum_tail_recursion(n - 1, acc + n)

sum_tail_recursion(4, 0) # 결과값 10

 

위 함수는

sum_tail_recursion(4, 0)
sum_tail_recursion(3, 4)
sum_tail_recursion(2, 7)
sum_tail_recursion(1, 9))
sum_tail_recursion(0, 10)

이런식으로 전개되어집니다.

 

 javascript engine이나 jvm, cpython은 기본적으로 tail recursion optimization을 지원하지 않아 stack-frame이 4개 그대로 생성되지만 gcc나 functional programming language는 tail recursion optimization을 지원하여 return 값을 받은 후 추가적으로 해야할 operation이 없는 경우 stack-frame을 덮어씌워 새로 생성하지 않고 recursion을 iteration으로 변환합니다.

결론은 Python에서는 재귀를 사용할 때 깊이가 너무 깊어지지 않도록 주의해야 하며, 깊이가 깊은 재귀가 필요한 경우에는 대체적으로 반복문을 사용하는 것이 권장됩니다.

 

반복문으로 위의 tail_recursion 함수를 바꾸면 이렇습니다.

def sum_loop(n, acc):
    while n != 0:
        acc += n
        n -= 1
    return acc

 

sum_loop는 while 루프를 돌며, n이 0이 될 때까지 acc에 n을 더하고, n을 1씩 감소시킵니다.

이 방식은 재귀에 비해 메모리 효율이 좋고, Python에서는 재귀 함수의 제한을 피할 수 있습니다.

이런 간단한 식이 아닌 복잡한 코드라면, 코드가 약간 더 길어지고, 이해하기 어려울 수 있습니다.