파이썬 재귀

파이썬 재귀

이 튜토리얼에서는 재귀 함수(자신을 호출하는 함수)를 만드는 방법을 배웁니다.

재귀란 무엇입니까?

재귀는 자체적으로 무언가를 정의하는 프로세스입니다.

물리적 세계의 예는 서로 마주하는 두 개의 평행 거울을 배치하는 것입니다. 그 사이에 있는 모든 객체는 재귀적으로 반영됩니다.

<시간>

파이썬 재귀 함수

파이썬에서는 함수가 다른 함수를 호출할 수 있다는 것을 알고 있습니다. 함수 자체를 호출하는 것도 가능합니다. 이러한 유형의 구성을 재귀 함수라고 합니다.

다음 이미지는 recurse라는 재귀 함수의 작동을 보여줍니다. .

<그림>

다음은 정수의 계승을 찾는 재귀 함수의 예입니다.

숫자의 계승은 1부터 해당 숫자까지의 모든 정수의 곱입니다. 예를 들어 6의 계승(6으로 표시됨)은 1*2*3*4*5*6 =720 입니다. .

재귀 함수의 예

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("The factorial of", num, "is", factorial(num))

출력

The factorial of 3 is 6

위의 예에서 factorial() 자신을 호출하는 재귀 함수입니다.

이 함수를 양의 정수로 호출하면 숫자를 줄여서 자신을 재귀적으로 호출합니다.

각 함수는 숫자가 1이 될 때까지 그 숫자 아래에 있는 숫자의 계승을 곱합니다. 이 재귀 호출은 다음 단계에서 설명할 수 있습니다.

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

진행 상황에 대한 단계별 프로세스를 보여주는 이미지를 살펴보겠습니다.

<그림>

숫자가 1로 줄어들면 재귀가 종료됩니다. 이것을 기본 조건이라고 합니다.

모든 재귀 함수에는 재귀를 중지하는 기본 조건이 있어야 합니다. 그렇지 않으면 함수가 자신을 무한히 호출합니다.

Python 인터프리터는 무한 재귀를 방지하기 위해 재귀 깊이를 제한하여 스택 오버플로를 발생시킵니다.

기본적으로 최대 재귀 깊이는 1000 입니다. . 제한을 초과하면 RecursionError이 됩니다. . 그러한 조건 중 하나를 살펴보겠습니다.

def recursor():
    recursor()
recursor()

출력

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

<시간>

재귀의 장점

1. 재귀 함수는 코드를 깔끔하고 우아하게 만듭니다.
2. 복잡한 작업은 재귀를 사용하여 더 간단한 하위 문제로 나눌 수 있습니다.
3. 재귀를 사용하면 일부 중첩 반복을 사용하는 것보다 시퀀스 생성이 더 쉽습니다.

<시간>

재귀의 단점

1. 재귀 이면의 논리를 따라가기 어려울 때가 있습니다.
2. 재귀 호출은 많은 메모리와 시간을 차지하므로 비용이 많이 듭니다(비효율적).
3. 재귀 함수는 디버그하기 어렵습니다.