재귀적 초보자 가이드

대부분의 프로그래밍 언어에서, 우리는 특정한 조건이 충족될 때까지 'while' 과 'for' 같은 순환 구조를 사용하여 코드 블록을 반복적으로 실행한다.귀속 함수가 하는 일은 기본적으로 같다.단지 그것은 내면의 자아 소환을 통해 실현된 것이다!순환 중처럼 어떤 조건을 충족시키면 자신을 사용하지 않는다.따라서 컴퓨터 프로그래밍에서 귀속은 함수가 자신을 호출하는 과정이다.
코드에서 반복은 다음과 같습니다.

def decrement_number_until_zero(number):
    print(number)
    decrement_number_until_zero(number - 1)

오, 괜찮아요?
그래, 그럴 리가 없어!왜?이 함수를 실행할 때, 덤프 넘침 오류를 던집니다.
스택 오버플로우 오류?
가장 기본적인 스택은 최상위 요소만 공개하는 데이터 구조입니다.굴뚝을 하나의 원기둥으로 상상해 한쪽은 열고 다른 한쪽은 닫는다.이런 원기둥에서, 너는 분명히 개구멍에 물건을 추가하고 제거할 수 있을 뿐이다.창고는 통상적으로 선진적인 데이터 구조라고 불린다.이것은 옳습니다. 창고는 창고 맨 위에서만 항목을 추가하고 삭제할 수 있기 때문에 창고에 들어가는 마지막 요소는 첫 번째 퇴출 요소이고, 첫 번째 퇴출 요소는 마지막 퇴출 요소입니다.스택에 요소를 추가하는 것은 밀어넣기, 스택에서 요소를 제거하는 것은 플라이아웃입니다.
그래, 네가 묻는 창고가 넘치는 것과 무슨 상관이야?
파이썬과 대부분의 프로그래밍 언어에서 함수 호출이 언제든지 이루어지면 함수는 호출 창고라고 불리는 창고 데이터 구조로 밀어넣는다.함수가 되돌아올 때, 함수는 호출된 창고에서 팝업됩니다.스택에 밀어넣는 모든 함수를 스택 프레임이라고 합니다.창고 프레임워크는 기본적으로 함수에 사용된 변수 등 정보와 함수가 되돌아와야 하는 위치를 저장한다.귀속 함수에서, 매번 함수가 자신을 인용할 때마다, 같은 함수를 호출 창고에 밀어넣는다.Python에서 창고를 호출할 때 수용할 수 있는 함수 수는 상한선이 있습니다.
우리의 함수는 호출 창고에 무한히 자신을 추가하려고 시도하기 때문에, 위의 함수는 창고 넘침 오류를 던질 것입니다.python의 호출 창고에 한도값이 있다는 것을 기억하십시오.한도값에 도달했을 때 덤프 넘침 오류를 던집니다.함수 정의가 함수 호출을 정지하는 조건을 지정하지 않았기 때문이다.이런 상황을 기본 상황이라고 부른다.따라서 이러한 함수를 작성하는 더 좋은 방법은 다음과 같습니다.

def decrement_number_until_zero(number):
    if number > 0:
        print(number)
        decrement_number_until_zero(number - 1)

이 수정된 함수는 무한 실행을 시도하지 않습니다. 왜냐하면 현재 실행을 중지해야 할 조건이 제공되었기 때문입니다.
다음은 두 번째로 돌아가는 예를 볼 수 있다.

def reverse_string_recursively(string):
     if len(string) == 0:
         return string
     else:
         return reverse_string_recursively(string[1:] )+ string[0]

위의 함수는 문자열을 차례로 반전시킨다.이것은 프로그램이 언제 실행을 끝낼 것인지를 지정하는 좋은 예이기도 하다.
발견한 바와 같이 좋은 귀속 함수는 두 부분으로 나뉜다.

기본 상황: 계산 결과가 '진짜' 일 때 프로그램 실행 종료

귀속case: 기본case의 계산 결과가false일 때 실행되는 부분입니다.일반적으로 이것은 함수가 자신을 인용하는 곳이다.

현재 나는 이미 호출 창고, 기본 상황, 귀속 상황에 관한 많은 내용을 이야기했다.나는 귀속 함수가 어떻게 백엔드에서 실행되는지 신속하게 보여 주었다.
역귀함수가 엔진 뚜껑 아래에서 실행되는 방식은 이야기를 하는 사람에 비유할 수 있다. 그가 말하는 것은 사람 a에 관한 이야기이다. 그리고 중간에 사람 B에 관한 이야기로 전환한 다음에 중간에 사람 C에 관한 이야기로 전환된다. 사람 C의 이야기가 끝날 때 이야기를 하는 사람은 이어서 사람 B에 관한 이야기로 돌아간다. 그/그녀는 거기에서 멈추었다.B인의 이야기가 끝날 때 이야기를 하는 사람이 이어서 계속 이야기하고 그/그녀가 끝난 곳에서 A인의 이야기를 완성한다.
몰라요?
우선, 우리는 이것이 일반 함수에서 어떻게 작동하는지 설명하는 예를 보았다.

def c():
    print(“at the beginning of c”)
    c()
    print(“at the end of c”)

def b():
    print(“at the beginning of b”)
    c()
    print(“at the end of b”)

def a():
    print(“at the beginning of a”)
    b()
    print(“at the end of a”)
a()

우선, 함수 a는 호출 창고에 불러옵니다. 이야기 설명자의 클래스와 같이, 실행 과정에서 주 실행 루틴은 함수 b로 전환되고, 거기에서도 함수 c로 전환됩니다. 함수 c가 실행을 끝낼 때 주 실행 루틴은 함수 b로 전환됩니다. 함수 a로 실행을 끝냅니다.
따라서 위 함수 a를 호출하는 출력은 다음과 같습니다.

at the beginning of a
at the beginning of b
at the beginning of c

at the end of c
at the end of b
at the end of a

앞에서 말한 바와 같이 함수의 마지막 줄을 실행할 때 함수가 되돌아온다.결과적으로 이 함수는 호출된 창고에서 팝업됩니다.
이게 어떻게 된 일인지 알기 시작했어?
자, 이게 귀속 함수에서 어떻게 작동하는지 봅시다.우리는 연구의 귀속 중의 흔히 볼 수 있는 문제를 통해 이 점을 이해할 수 있다. 즉, 하나의 수의 곱셈을 찾는 것이다.

def factorial(number):
    """factorial recursive implementation"""
    if number <0:
        return -1
    elif number < 2:
        return 1
    else:
       return number * factorial(number-1)

factorial(5)

먼저 곱하기(5)*5라고 합니다.그러나 5가 2보다 크기 때문에 곱하기(5)는 곱하기(5-1)*5-1에 대한 호출을 다시 촉발합니다.지정한 조건 중 하나가true로 계산될 때까지 계속됩니다.이것은 호출 곱하기 (1) 시 발생합니다.1이 2 단계 곱하기보다 작기 때문에 (1) 값을 되돌려 창고에 있는 다음 함수에 전달합니다.물론 곱하기 (1)*1이 돌아오면 창고에서 튀어나옵니다.이런 식으로 상상하면
단계 승(1)*1
계승(2)*2
계승(3)*3
곱하기
계승(5)5
밑에 있는 항목은 호출 창고에 불러오는 첫 번째 항목입니다.
1이 2보다 작기 때문에, 우리의 함수 정의에 따라 곱하기 (1) 는 1을 되돌려주고, 출력을 1로 곱합니다.그리고 위층의 결과를 아래 함수에 전달한다. 1 곱셈에 전달한다(2).곱하기(2) 그리고 전달된 내용을 되돌려주고 출력 1 곱하기 2.따라서 2층은 2로 되돌아와 다음 함수, 즉 곱하기(3)에 다시 전달한다.그것은 창고 밑에 있는 함수가 돌아올 때까지 이런 식으로 계속된다.
이것이 바로 귀속 함수의 집행 방식이다!
아니면 몰라요?
그럼 귀환을 포기하고 순환을 계속 사용하세요...하하
그러나 솔직히 말하면 어떤 귀속 함수도 순환으로 실현할 수 있다.예를 들어 위의 역방향 문자열과 계승 함수는 다음과 같은 순환을 사용할 수 있다.

def reverse_string(string):
“””iterative implementation”””
    length = len(string) - 1
    reversed_string = " "

    while length >= 0:
        reversed_string += string[length]
        length -= 1
    return reversed_string

def factorial(number):
    """iterative implementation of factorial"""

    if number <0:
        return -1
    elif number < 2:
        return 1
    else:
        factorial = 1

        for num in range(1, number+1):
            factorial = factorial * num
        return factorial

그 밖에 교체해에 비해 귀속해가 반드시 더 좋은 공간과 시간 복잡도를 가지는 것은 아니다.사실상, 귀속 함수가 반복적으로 호출 창고에 창고 프레임을 추가하기 때문에, 사람들은 심지어 그들의 공간 복잡도가 매우 나쁘다고 말할 수 있다.귀속 해결 방안이 더욱 우아하다.!얘네가 더 깔끔해!이것은 반대로 코드의 가독성을 높였고 확장을 통해 코드의 질을 높였다.
도구책
Freecodecamp: How Recursion Works Explained