귀속-귀속이 만족해야 할 두 가지 조건

많은 사람들이 귀속에 대한 이해가 그리 깊지 않다.스스로 자신을 호출하는 정도에 머물렀다.이것은 사실 귀환의 표상일 뿐이다.돌아가는 사상은 이뿐만이 아니다.
귀환은 단순한'자기 호출'도 아니고 간단한'자기 호출'도 아니다.그것은 문제를 분석하고 해결하는 방법과 사상의 일종이다.간단하게 말하자면 귀착된 사상은 문제를 규모가 더 작고 원문제와 같은 해법을 가진 문제로 분해하는 것이다.예를 들어 이분 검색 알고리즘은 끊임없이 문제의 규모를 작게 (원문제의 반으로 바꾸고) 새로운 문제는 원문제와 같은 해법을 가지고 있다.
어떤 문제는 전통적인 교체 알고리즘을 사용하면 풀기 어렵고 심지어 풀리지 않지만 귀속을 사용하면 쉽게 해결할 수 있다.예를 들면 한노타 문제.그러나 귀환의 사용도 열세가 있다. 다층 함수 호출을 해야 하기 때문에 많은 창고 공간과 함수 호출 시간을 소모할 수 있다.
귀착의 사상은 문제를 규모가 더 작고 원문제와 같은 해법을 가진 문제로 분해하는 것이니 이런 문제를 모두 귀착으로 해결할 수 있지 않겠는가?답안은 부정적이다.모든 문제를 귀속으로 해결할 수 있는 것은 아니다.그러면 어떤 문제를 귀환으로 해결할 수 있습니까?일반적으로 반복으로 해결할 수 있는 문제는 반드시 두 가지 조건을 만족시켜야 한다.
역귀조를 통해 문제의 규모를 축소할 수 있고 새로운 문제는 원래의 문제와 같은 형식을 가진다.간단한 상황이 존재하여 간단한 상황으로 돌아가 퇴출할 수 있다.만약 한 문제가 상기 두 가지 조건을 만족시키지 못한다면, 그것은 귀환으로 해결할 수 없다.
이해하기 편리하도록 피보나치 수열로 말하자면 피보나치 수열의 N항의 값을 구한다.
이것은 고전적인 문제로, 귀환하면 반드시 이 문제를 제기해야 한다.피보나치 수열은 다음과 같이 정의한다. f(0)=0, f(1)=1, n>1, f(n)=f(n-1)+f(n-2)
이것은 명백히 귀속적으로 해결할 수 있는 문제다.귀속의 두 가지 조건을 어떻게 충족시키는지 살펴보자.
n>2에 대해 f(n)를 구하는 데는 f(n-1)와 f(n-2)만 필요하다. 즉, 규모가 n인 문제는 규모가 더 작은 문제로 바뀌었다.n=0과 n=1에 대해 간단한 상황이 존재한다. f(0)=0, f(1)=1.따라서 우리는 페포나치 수열을 계산하는 n항의 귀속 프로그램을 쉽게 쓸 수 있다.

int fib(n){
    if(n == 0)
       return 0;
    else if(n == 1)
      return 1;
    else
        return f(n-1) + f(n-2);
}

귀속 호출 함수를 작성할 때, 반드시 간단한 상황에 대한 판단을 맨 앞에 써야 한다. 함수 호출이 간단한 상황을 검사할 때 제때에 귀속을 중지할 수 있도록 해야 한다. 그렇지 않으면, 당신의 함수는 영원히 그곳에서 귀속 호출을 멈추지 않을 것이다.
만담 귀속: 귀속에 필요한 두 가지 조건