개발자 사전 - 귀속

만약 당신이 큰 복잡한 문제를 해결할 수 있다면, 작은 문제나 간단한 문제를 해결함으로써 그것을 해결할 수 있습니까?
상상해 보세요.비교적 작은 사이즈를 계산하는 문제의 해답.그리고이 자해를 수중에 있는 더 큰 문제의 최종해와 연결시키다.이것은 컴퓨터 프로그램에서 귀속 개념의 본질이다.귀속은 구체적인 예로 설명하는 것이 가장 좋다. 여기에는 두 가지가 있다.

예제 1 피보나치 시퀀스

너는 아마도 학교의 피보나치 서열을 기억하고 있을 것이다.이것은 일련의 숫자인데, 그 중에서 각 숫자는 앞의 두 숫자의 총체이다.1, 1, 2, 3, 5, 8, 13, 21, 34, 55이것은 상위 10개의 피보나치수다.n번째 피보나치수로 되돌아오는 함수fib를 작성해 보세요.따라서 n=10의 경우 55, 즉 34+21로 되돌아간다.정의는 다음과 같습니다.fib(n) = fib(n-1) + fib(n-2)오른쪽에서 우리가 호출하는 함수는 우리가 정의하려고 하는 함수와 같다는 것을 주의하십시오.이것은 귀속 함수 정의입니다.귀속 함수를 정의하는 것은 두 가지 일과 관련이 있다. 작은 입력으로 같은 함수를 호출하고 기본적인 상황을 정의하는 것이다.귀속 함수 호출이 표시됩니다.피보나치 서열의 정의를 보면 이것은 직감적으로 의미가 있다.기본 상황은 무엇입니까?
기본적인 상황은 함수가 자신을 호출하지 않는 상황에서 값을 되돌릴 수 있는 방식이다.함수 호출 체인을 끝내는 방법이 필요하기 때문이다.이 경우 기본 상황은'n=1 또는 n=2 시 1만 반환'이라고 정의할 수 있다.기본 상황을 정의할 때, 우리는 어떠한 귀속 함수 호출도 하지 않는다.

위의 그림에서 우리의 목표는 다섯 번째 피보나치 수를 계산하는 것이다.우리는 네 번째와 세 번째fib수를 합쳐 답을 얻을 수 있다는 것을 직관적으로 알고 있다.컴퓨터 프로그램은 어떻게 귀속적으로 그것을 실행합니까?
주황색 화살표는 기본 상황을 나타낸다.녹색 숫자는 이전 함수에서 호출된 답을 얻기 위해'집합'을 추가할 수 있는 답안입니다.다섯 번째fib수를 계산하기 위해 우리는 최종적으로 8번의fib함수를 호출한 것을 볼 수 있다.다음은 함수 정의입니다.

function fib(n) {
    if (n <= 2) return 1;

    return ( fib(n-1) + fib(n-2) );
}

하노이 타워

가능하다면 이것Tower of Hanoi game을 틀어 규칙을 느껴보세요.디스크 수가 증가함에 따라 게임이 왜 빨리 도전적인지 체험할 수 있습니다.
하노이 타워의 목표는 모든 디스크를 원본 peg A에서 목표 peg B로 이동하는 동시에 peg C를 임시 저장 장소로 사용하는 것이다.두 가지 기본 규칙이 있습니다. 한 번에 하나의 디스크만 이동할 수 있고 언제든지 큰 디스크를 작은 디스크에 놓을 수 없습니다.
세 개의 디스크가 있는 탑을 상상해 보자.너는 그것을 쉽게 이동할 수 있다. 너는 모든 절차를 미리 상상할 수 있고, 너는 이런 동작을 상상할 수 있다.3개의 디스크를 이동하는 과정이 10개의 디스크, 25개의 디스크, 50개 또는 100개의 디스크로 옮겨질 수 있다고 믿습니까!
그러나 우리 대다수 사람들은 이런 동작을 미리 상상할 수도 머릿속에 기억할 수도 없다.3개 디스크의 이동 횟수는 7이다.4개 디스크의 경우 15, 5개 디스크의 경우 31.이것은 일리가 있다. 우리는 세 개의 디스크를 초과하는 절차를 상상할 수 없다.연구에 따르면 우리의 뇌는 단기 기억에서 4~7개의 다른 것만 보존할 수 있다.이런 상황에서 이동 횟수는 디스크 수에 따라 지수적으로 증가한다.
귀속의 개념을 하노이타워에 응용하면 우리는 논리에 맞는 곳을 얻을 수 있다. 그곳에서 우리는 우리가 어떤 숫자 n의 게임도 해결할 수 있다고 믿는다(충분한 시간과 인내심을 주어라!).다음은 우리가 어떻게 해결 방안을 직관적으로 생각하는지: n개의 디스크를 Peg A에서 Peg B로 이동하기 위해서는 어떻게 해야 하는지 알아야 한다.

n-1개의 원반을 핀 A에서 임시 핀 C로 이동합니다.

그리고 마지막 원반(최대 원반)을 핀 A에서 핀 B로 이동합니다.

그리고 1단계에서 사용된 동일한 절차를 사용하여 현재 Peg C에 있는 n-1개의 디스크를 Peg B, 즉 대상 Peg로 이동합니다.

결국 모든 n 개의 디스크가 Peg B에 위치하고 이것이 목표입니다.
너는 이 해결 방안의 본질이 귀속의 개념이라는 것을 볼 수 있다.그러면 기본 상황은요?기본 상황은 n=1 디스크입니다.그래, 이거 쉬워. 그렇지, 우리는 단지 그것을 주워서 이동할 뿐이야.그래서 너는 내가 디스크를 어떻게 이동하는지 알면 100개의 디스크를 어떻게 이동하는지 안다고 생각할 수도 있다.네, 완전히 정확합니다.이것은 직감적인 만족을 느끼지 못할 수도 있지만, 이것은 정말이다.100개의 디스크를 이동하려면 99개의 디스크를 이동하는 방법을 알아야 합니다.그러나 99개의 디스크를 이동하려면 98개의 디스크를 이동하는 방법만 알아야 합니다...3개의 디스크를 이동하려면 2개의 디스크를 이동하는 방법만 알고 2개의 디스크에 대해서는 1개의 디스크를 이동하는 방법만 알고 있어야 합니다.아하!우리는 이 점을 어떻게 하는지 안다. 이것은 우리의 기본적인 상황이다.
[그나저나 우리는 100개의 디스크를 어떻게 이동하는지 알고 있지만, 이것은 간단하거나 힘을 절약하는 것을 의미하지는 않는다. 우리가 앞에서 본 바와 같이 이동하는 횟수가 매우 빨리 증가한다. 100개의 디스크에 대해서는 2100-1개의 이동이 필요하다. 이것은 31비트 길이의 10진수이다!]
이제 너는 프로그래밍에서 돌아가는 본질을 알게 되었다.너는 이것이 매우 강력한 개념이라는 것을 볼 수 있다.우리는 해결 방안의 모든 절차를 상상하거나 머릿속에서 파악할 수 없지만, 우리는 컴퓨터 프로그램을 쉽게 작성하여 이런 방식으로 문제를 해결할 수 있다.