Python의 꼬리 재귀

1. 파이썬의 재귀
2. Python의 꼬리 재귀
3. Python에서 테일 재귀 함수 호출
4. 꼬리 재귀 함수의 이점

오늘 튜토리얼에서는 재귀와 그 종류를 통해 테일 재귀에 대해 알아봅니다. 또한 Python에서 꼬리 재귀를 호출하는 방법을 배우고 이를 사용하는 몇 가지 이점을 살펴봅니다.

파이썬의 재귀

컴퓨터 과학에서 재귀는 함수가 특정 조건이 충족될 때까지 본문에서 자신을 호출하는 문제 해결 방법입니다.

이것은 가치있는 방법 중 하나이며 실제 사용 사례가 많습니다. 그러나 몇 가지 제한 사항이 있으며 이는 공간 및 시간 복잡성입니다. 아래에서 재귀의 예를 살펴보겠습니다.

예제 코드:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)  # recursive call


num = 4

# In this case factorial is 4x3x2x1 = 24
print(f"The factorial of {num} is {factorial(num)}")

출력:

The factorial of 4 is 24

재귀는 스택을 사용하여 로컬 변수를 유지하고 재귀를 실행할 때마다 크기가 증가하며 스택 크기는 제한됩니다. 이것이 개발자들이 일부 최적화된 솔루션에 대해 생각하기 시작한 이유입니다.

소수에만 적합합니다. 그래서 개발자들이 단순 재귀의 최적화된 솔루션을 생각해 냈고, 그것이 Tail Recursion입니다.

재귀의 유형

재귀 함수에는 두 가지 주요 유형이 있습니다.

1. 헤드 재귀
2. 꼬리 재귀

헤드 재귀는 함수가 처음에 자신을 호출하는 경우이고 꼬리 재귀는 함수가 재귀의 끝에서 자신을 호출하는 경우입니다.

둘 다 장점과 단점이 있지만 일반적으로 꼬리 재귀가 더 효율적인 것으로 간주됩니다. 아래에서 더 자세히 이해합시다.

Python의 꼬리 재귀

Python의 꼬리 재귀는 단순 재귀에 최적화된 솔루션입니다. 스택 오버플로 오류를 발생시키지 않고 무제한 재귀를 허용합니다.

그러나 꼬리 호출 재귀에 대해 자세히 알아보기 전에 꼬리 호출 재귀의 정의를 이해해 봅시다. call은 함수 호출을 고려하고 있음을 의미하고 tail은 마지막을 의미합니다. 따라서 tail-recursive 메서드를 호출한다는 것은 함수가 함수의 끝에서 반복적으로 자신을 호출한다는 것을 의미합니다.

오늘날 대부분의 프로그래밍 언어는 꼬리 재귀적이며, 이는 재귀 함수를 최적화하고 있음을 의미합니다.

Python에서 테일 재귀 함수 호출

Python에서 꼬리 재귀 함수를 호출하는 방법에는 두 가지가 있습니다. 첫 번째는 return 키워드를 사용하는 것이고 두 번째는 yield 키워드를 사용하는 것입니다.

return 키워드를 사용하여 꼬리 재귀 함수 호출

먼저 return 키워드를 사용하여 함수에서 값을 반환할 수 있습니다. 그러나 이 키워드는 함수를 즉시 종료하므로 주의해야 합니다.

이는 함수를 다시 호출할 필요가 없다고 확신하는 경우에만 사용할 수 있음을 의미합니다. ‘return’ 키워드를 사용할 때 함수는 마지막으로 계산된 값을 반환합니다.

꼬리 재귀 함수를 호출하는 가장 일반적인 방법입니다. 예를 들어 아래 코드 펜스를 참조하세요.

예제 코드:

def trisum(n, csum):
    while True:  # Change recursion to a while loop
        if n == 0:
            return csum
        n, csum = n - 1, csum + n  # Update parameters instead of tail recursion


trisum(1000, 0)

출력:

500500

yield 키워드를 사용하여 꼬리 재귀 함수 호출

꼬리 재귀 함수를 호출하는 또 다른 방법은 yield 키워드를 사용하는 것입니다. 이 키워드를 사용하면 함수를 종료하지 않고 함수에서 값을 반환할 수 있습니다.

함수를 반복적으로 호출하여 매번 다른 값을 반환할 수 있습니다. 많은 수의 값을 반환해야 하는 함수에 편리합니다.

yield 키워드를 사용할 때 함수는 마지막으로 계산된 값을 yield합니다. 꼬리 재귀 함수를 호출하는 덜 일반적인 방법이지만 경우에 따라 도움이 될 수 있습니다.

예제 코드:

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a


b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

출력:

1
2
3
4
5
6
7
8
9

꼬리 재귀 함수의 이점

꼬리 재귀 함수는 함수의 마지막 문이 재귀 함수에 대한 호출인 재귀 함수 유형입니다.

이 함수는 함수가 재귀 호출의 중간 값을 추적할 필요가 없기 때문에 꼬리가 아닌 재귀 함수보다 더 효율적입니다.

꼬리 재귀 함수를 보다 효율적이고 이해하기 쉽게 만듭니다. 꼬리 재귀 함수를 사용하면 많은 이점이 있습니다.

1. 꼬리 재귀의 주요 이점 중 하나는 최적화하기가 더 쉽다는 것입니다. 꼬리 호출은 함수에서 마지막으로 발생하기 때문에 컴파일러는 이를 더 쉽게 최적화할 수 있습니다. 이는 꼬리 재귀 함수가 시간과 공간 측면에서 더 효율적일 수 있음을 의미합니다.
2. 꼬리 재귀의 또 다른 이점은 종종 이해하기 쉽다는 것입니다. 재귀 호출은 함수에서 일어나는 마지막 일이기 때문에 무슨 일이 일어나고 있는지 더 쉽게 볼 수 있습니다. 꼬리 재귀 함수를 디버그하고 유지 관리하기 쉽게 만들 수 있습니다.
3. 중간 값을 추적할 필요가 없기 때문에 꼬리가 아닌 재귀 함수보다 더 효율적입니다.
4. 함수 호출 스택은 함수 끝에서 항상 비어 있기 때문에 추론하기가 더 쉽습니다. 또한 꼬리 재귀 함수는 더 쉽게 병렬화할 수 있습니다.
5. 어떤 경우에는 더 효율적일 수 있는 반복 프로그램으로 쉽게 변환할 수 있습니다.
6. 기능을 더 빠르게 실행하고 메모리를 적게 사용할 수 있습니다. 또한 올바른 코드를 더 쉽게 작성할 수 있습니다.