빠른 입문 알고리즘 사상: 귀속

인터넷상에서 귀환에 대해 많은 설명 방법이 있는데 예를 들면 생동감 있고 형상적이다. 나는 하나의 예를 골라서 귀환이라는 사상을 끌어낸다.

 ， ， ， ， ， ， 

이 예는 모두가 귀에 익어 자세히 알 수 있는데, 신문 안이든 신문이든 그다지 엄격하지 않은 정의를 내린다. 바로 함수 자체가 자신을 호출하여 문제를 해결하는 것이다.
귀속이라는 두 글자도 함부로 이런 이름을 지은 것이 아니니, 귀속의 사상을 이해하면 서면으로 분석할 수 있다
이른바 점차: 큰 문제를 같은 사상으로 해결할 수 있는 하위 문제로 분해하여 분리할 수 없을 때까지 층층이 파라미터를 아래로 건네주는 것이다.
이른바 귀착이란 매개 변수를 층층이 아래로 건네주고 어떤 조건을 만족시킬 때까지 매개 변수가 되돌아오는 것이다. 그러면 회귀의 과정이 시작되고 큰 문제가 해결될 때까지 층층이 되돌아간다.
전반적으로 말하면 귀속은 두 가지 특징이 있다.
1. 큰 문제는 같은 방법으로 해결된 하위 문제로 분해한다(코드에 나타난 것은 함수 호출이다)
2. 층층이 분해된 하위 문제는 마지막에 분해할 수 없는 고정값(즉 귀속의 종지 조건)에 도달할 것이다.
 
여기에 와서 귀환에 대해 초보적인 인상을 가져야 한다. 문제를 풀기 전에 우리는 반드시 귀환으로 문제를 풀 수 있는 고정된 방법을 알아야 한다. 그렇지 않으면 초학에서 사고방식을 찾기 어렵다.
또한 하나의 문제를 설명해야 한다. 귀속은 일종의 프로그래밍 기교이고 문제를 해결하는 사고방식이다.분치 알고리즘과 동적 기획은 어느 정도에 귀속 사상을 바탕으로 하는 것이다(동적 기획의 최종 버전은 대부분 귀속이 아니지만 문제 풀이 사상은 귀속을 떠날 수 없다). 더욱 구체적인 문제를 해결하는 두 가지 알고리즘 사상.욕심 알고리즘은 동적 기획 알고리즘의 서브집합으로 일부 특수한 문제를 더욱 효율적으로 해결할 수 있다. 만약에 분해된 문제에 중복 계산이 존재한다면 동적 기획으로 해결하는 것이 가장 좋다.
문제 풀이 방법:
1. 먼저 함수(방법)의 기능을 정의한다. 함수 내부에서 어떻게 실현되든지 간에 먼저 이 함수가 무엇을 하는지 알아야 한다(일반적인 기능은 제목의 문제), 함수의 역할을 이해하고 이 임무를 완성할 수 있다고 믿어야 한다. 절대로 세부 사항에 뛰어들려고 하지 마라.절대로 이 함수에 뛰어들어 더 많은 세부 사항을 탐구하려 하지 마라. 그렇지 않으면 무한한 세부 사항에 빠져 빠져나갈 수 없다. 종지 조건을 찾지 못하면 뇌는 이 문제에 대해 무한히 깊이 들어가게 된다. 초보자는 항상 이곳에서 무한히 귀속되어 바로 끊긴다.
2. 그리고 위에서 아래로의 분석 문제(큰 문제 분해자 문제, n단계는 n-1단계로 어떻게 표시하는가)를 찾아 점차적인 공식과 종지 조건을 찾는다.
3. 추이 공식과 종지 조건을 첫 번째 정의의 함수에 보충
 
이 세 가지 문제 풀이 방법이 있으면, 바로 문제에 올라가서, 구체적인 문제를 어떻게 이 세 가지 방법으로 해결하는지 살펴보자.
먼저 가장 간단한 문제로 n의 곱셈을 구하고, 문제 풀이의 틀에 따라 문제 풀이의 방향을 찾아라.

1.  
    #  ： n 
    def factor(n):
        pass

2. 
     ， n n-1 ， n！= n-1！* n
     factor n ， n-1 
     factor(n)=factor(n-1)*n
     n=1 factor(1)=1

3. 
    def factor(n):
        if n==1: return 1
        return fasctor(n-1)*n

체계적인 방법에 따라 곧 문제를 풀 방향을 찾을 수 있다. 물론 이 문제는 비교적 간단하지만, 다음에 한 문제를 더 하겠다.

  1   2  ， ：   1  ：  1  。   2  ：  1  ， ；  2  。   n  ？

같은 방법으로 이 개구리가 계단을 뛰어넘는 문제를 분석하다

1. ： n 
    def jump(n):
        pass

2. 
   ， n n-1 
   n n-1 n-2 ， n = (n-1)+(n-2)
   jump(n)=jump(n-1)+jump(n-2)
    n=1 jump(1)=1; n=2 jump(2)

3. 
    def jump(n):
        if n==1: return 1
        if n==2: return 2
        return jump(n-1)+jump(n-2)

        

이런 분석을 통해 귀속에 대해 약간의 감각이 생겼는지 이 과정이 익숙하지 않은지 고등학교 때 수열을 배울 때 그 수열의 추이 공식이 생각났는지!
역방향 사고 능력을 훈련시키는 것이다. 점차적인 사고는 정상인의 사고이고 항상 눈앞의 문제를 보고 대책을 생각하며 문제를 해결하는 것은 장래이다.돌아가는 사고는 우리로 하여금 거꾸로 생각하게 하고 문제의 끝을 보게 하며 문제를 해결하는 과정을 과거시로 간주하게 한다.
귀속적인 방법으로 작성된 코드는 간결하지만 실제적으로 중간에 매우 많은 반복 절차가 있기 때문에 다른 방법으로 점차적으로 최적화할 수 있다. 그리고 이것은 귀속의 입문일 뿐이다. 뒤에 더욱 어려운 문제가 있어 유연하게 분석해야 한다. 그러나 만변해도 그 근본을 벗어나지 않는다. 귀속의 가장 기본적인 사상은 대체로 이렇다. 네가 사고방식을 찾지 못할 때 해법에 따라 한 걸음 한 걸음 분석해 보는 것도 괜찮다.
마지막으로 귀속사상을 진정으로 이해했는지 검증하려면 아래의 몇 가지 문제에 대답하기만 하면 된다
4

어떻게 한 무더기의 숫자를 정렬합니까?답:반으로 나눠서 왼쪽과 오른쪽을 먼저 정하고 오른쪽을 정하고 마지막에 합치면 돼요. 왼쪽과 오른쪽을 어떻게 정하는지는 이 말을 다시 읽어주세요

손오공의 몸에는 털이 얼마나 있습니까?답:털 한 가닥에 남은 털
올해 몇 살이에요?답: 작년에 나이를 한 살 더 먹고 1994년에 태어났어요