데이터 구조와 알고리즘(6): 귀속

귀속

이른바 귀속이란 간단하게 말하자면 하나의 함수가 직접 또는 간접적으로 자신을 호출하는 방법으로 통상적으로 하나의 대형 복잡한 문제를 층층이 원래의 문제와 비슷한 규모가 비교적 작은 문제로 바꾸어 해답을 구한다.
큰 놈의 예를 인용하다.
우리는 '귀속' 을 '사전 찾기' 에 비유할 수 있다. 네가 한 단어를 찾아보면, 이 단어의 해석 중의 어떤 단어가 여전히 이해하지 못하는 것을 발견하고, 그래서 너는 이 두 번째 단어를 찾기 시작한다.
아쉽게도 두 번째 단어에 아직도 모르는 단어가 있다. 그래서 세 번째 단어를 찾아라. 이렇게 조사해 보면 한 단어의 해석이 네가 완전히 이해할 수 있을 때까지 끝까지 돌아간다. 그리고 너는 뒤로 물러나기 시작한다. 전에 조사한 단어 하나하나를 하나하나 알아낸다. 결국 너는 처음에 그 단어의 뜻을 분명히 밝혔다.
우리는 사전 검색을 하나의 함수 search(){} 로 이해했고, '알았다' 는 정지 조건이었다.
이 사고방식에 따르면 이 절차는 바로 이렇다.

public void search(){
    // 
    if(" "){
       return;
    }
    // 
    search();
}

우리는 간단한 예를 들자.
다음 코드를 사용하여 단계 곱하기1*2*3*.....*(n-1)*n를 계산합니다.

public static int mult(int n) {
    // ， n=1 1
    if (n == 1){
        return n;
    }
    // n*(n-1).....
    return n * mult(n - 1);
}

2. 귀속과 창고의 관계

귀속 과정은 바로 창고에 출입하는 과정이다
귀속된 문제는 사실상 모두 출입창고 문제로 나눌 수 있다. 우리는 상기 계산1*2*3*.....*(n-1)*n이라는 예를 들어 이해할 수 있다.
만약 n=4라면 과정은 이렇다.

mult(4)mult(3)

호출

mult(3)mult(2)

호출

mult(2)mult(1)

호출

mult(1)에 도달했을 때 종료 조건을 만족시키고 결과를 되돌려준다

출입 창고의 사유로 이해하다.

단계 1-3은 모두 입고 과정이고mult(4)는 결과를 계산한 후 입고한 다음mult(3)를 실행하여 결과를 얻어 입고한다.이와 같이 유추

n=1의 정지 조건에 도달했을 때 귀속 정지는 재입고하지 않는다. 이때 창고의 깊이는 4이다. 이것도 귀속 깊이

라고 한다.

정지 조건을 충족시킨 후 출고, mult(1)의 결과는 출고, mult(2)의 결과는 출고와 곱하고, 뒤이어 출고된 mult(3)의 결과는 곱하기......이와 같이 유추

귀속의 본질은 바로 창고의 출입 과정이기 때문에 실제 깊이가 너무 깊어서 jvm가 규정한 창고의 최대 깊이를 초과할 때 창고가 넘치는 문제가 발생한다. 즉java의StackOverflowError

3. 귀속적인 사용 조건

그러면 우리는 귀환을 사용하여 문제를 해결할 때가 되었다.

문제는 하위 문제로 나눌 수 있고 하위 문제는 원래 문제의 해결 방법과 같다

절차 정지 조건이 명확하다

예를 들어 앞의 글에서 연속 곱셈 문제를 언급한 것이 전형적인 예이다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조와 알고리즘(6): 귀속

귀속

2. 귀속과 창고의 관계

3. 귀속적인 사용 조건

좋은 웹페이지 즐겨찾기