실습 14일차(Recursion)

귀착사상

귀속은 하나의 과정을 가리킨다. 함수는 인용의 대상이 알 때까지 끊임없이 자신을 인용한다.귀환은 함수 내부에서 자신의 함수를 호출하는 것을 귀환이라고 부른다.주말에 너는 여자 친구를 데리고 영화관에 가서 영화를 보는데, 여자 친구가 너에게 묻는다. 우리는 지금 몇 줄에 앉아 있니?영화관 안이 너무 어두워서 잘 안 보여서 셀 수가 없어요. 이제 어떡해요?귀속사상: 앞줄에 있는 사람에게 그가 몇 번째 줄인지 물어봐라. 그의 숫자에 1을 더하면 자신이 어느 줄에 있는지 알 수 있을 거야.그런데 앞사람도 잘 안 보이네요. 그래서 앞사람한테도 물어봤어요.이렇게 한 줄 한 줄 앞으로 가서 첫 번째 줄에 있는 사람에게 내가 첫 번째 줄에 있다고 말할 때까지 물었다. 그리고 이렇게 한 줄 한 줄 숫자를 되돌려 주었다.네 앞에 있는 사람이 너에게 그가 어느 줄에 있는지 알려줄 때까지 너는 답을 알게 될 것이다.이것은 매우 표준적인 귀속 구해 문제의 분해 과정으로 가는 과정을'집'이라고 하고 돌아오는 과정을'귀'라고 한다.기본적으로 모든 귀속 문제는 추이 공식으로 표시할 수 있다.방금 이 예에서 우리는 추이 공식으로 그것을 나타낸다. f(n)=f(n-1)+1 그 중에서 f(1)=1 f(n)는 네가 어느 줄에 있는지 알고 싶다는 뜻이고, f(n-1)는 앞에 있는 줄의 수를 의미하며, f(1)=1은 첫 번째 줄의 사람이 자신이 첫 번째 줄에 있다는 것을 안다는 뜻이다.

귀속되는 세 가지 조건

방금 이 예는 매우 전형적인 귀착이다. 그러면 도대체 어떤 문제를 귀착으로 해결할 수 있을까?나는 세 가지 조건을 총결하였는데, 아래의 세 가지 조건을 동시에 만족시키기만 하면, 귀환으로 해결할 수 있다.

한 문제의 해답은 몇 개의 하위 문제의 해답으로 분해할 수 있는데 무엇이 하위 문제입니까?하위 문제는 데이터 규모가 더 작은 문제다.예를 들어 앞에서 말한 영화관의 예를 들면'자신이 어느 줄에 있느냐'는 문제는'앞줄의 사람이 어느 줄에 있느냐'는 하위 문제로 분해할 수 있다는 것을 알아야 한다.

이 문제는 분해된 후의 하위 문제와 데이터 규모가 다른 것을 제외하고 해답을 구하는 사고방식은 완전히 같다. 예를 들어 영화관의 그 예에서 너는'자신이 어느 줄에 있느냐'는 사고방식을 구하고 앞줄의 사람이'자신이 어느 줄에 있느냐'는 사고방식과 똑같다.

귀속종지조건이 존재하여 문제를 자문제로 분해하고 자문제를 자문제로 분해한다. 한 층 한 층 분해하면 무한순환이 존재하지 않기 때문에 종지조건이 필요하다.아니면 영화관의 예에서 첫 번째 줄의 사람들은 누구에게도 계속 물어보지 않아도 자신이 어느 줄에 있는지 알 수 있다. 즉, f(1)=1이다. 이것이 바로 귀환의 종지 조건이다.

반복 사례 작성

만약에 여기에 n개의 계단이 있다면 매번 당신은 1개의 계단 또는 2개의 계단을 건널 수 있습니다. 이 n개의 계단을 걷는 방법은 몇 가지가 있습니까?만약 7개의 계단이 있다면 너는 2, 2, 1, 이렇게 올라갈 수도 있고, 1, 2, 1, 1, 2, 이렇게 올라갈 수도 있다. 어쨌든 걷는 방법이 매우 많은데, 어떻게 프로그래밍으로 총 몇 가지 걷는 방법이 있는지 구할 수 있겠니?우리가 곰곰이 생각해 보면 실제로 첫 번째 걸음걸이에 따라 모든 걸음걸이를 두 종류로 나눌 수 있다. 첫 번째 걸음걸이는 한 계단, 다른 한 걸음걸이는 두 계단으로 나눌 수 있다.그래서 n계단의 걷는 방법은 먼저 1계단을 걷고 n-1계단을 걷는 방법과 먼저 2단계를 걷고 n-2단계를 걷는 방법과 같다.공식으로 표현하면 다음과 같다.

f (n) = f(n  - 1) + f(n - 2)

추이 공식이 생겨서 귀속 코드는 기본적으로 반을 완성했다.종지 조건을 다시 한 번 봅시다.계단이 하나 있을 때, 우리는 더 이상 돌아갈 필요가 없다. 단지 하나의 걷는 방법일 뿐이다.그래서 f(1)=1.이 귀속 종지 조건은 충분합니까?우리는 n=2, n=3 이렇게 비교적 작은 수로 시험해 볼 수 있다.n=2시, f(2)=f(1)+f(0).만약 귀속 중지 조건이 f(1)=1만 있다면 f(2)는 해답을 구할 수 없습니다.그래서 f(1)=1이라는 귀속 종지 조건을 제외하고 f(0)=1도 있다. 이것은 0계단을 걷는 데 걷는 방법이 있다는 것을 의미하지만 이렇게 보면 정상적인 논리적 사고에 부합되지 않는다.그래서 우리는 f(2)=2를 일종의 종지 조건으로 삼아 두 계단을 걷는 것을 나타낼 수 있다. 두 가지 걷는 방법이 있는데 한 걸음이 끝나거나 두 걸음으로 나뉜다.따라서 귀속 중지 조건은 f(1)=1, f(2)=2이다.이때 당신은 n=3, n=4를 가지고 이 종지 조건이 충분하고 정확한지 검증할 수 있습니다.우리는 귀속 종지 조건과 방금 얻은 추이 공식을 함께 놓으면 다음과 같다.

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

이 공식이 있으면 우리는 귀속 코드로 전환하는 것이 훨씬 간단해진다.최종 귀속 코드는 다음과 같습니다.

  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

요약:

하나, 귀환은 무엇입니까?1. 귀속은 매우 효율적이고 간결한 인코딩 기교로 매우 광범위하게 응용되는 알고리즘이다. 예를 들어 DFS 깊이 우선 검색, 전·중·후순 두 갈래 트리 스트리밍 등은 모두 귀속을 사용한다.2. 방법이나 함수가 자신을 호출하는 방식을 귀속호출이라고 하고 호출을 배달이라고 하고 귀환을 귀라고 한다.3. 기본적으로 모든 귀속 문제는 추이 공식으로 나타낼 수 있다. 예를 들어 f(n)=f(n-1)+1;f(n) = f(n-1) + f(n-2); f(n)=n*f(n-1);

2. 왜 귀속을 사용합니까?귀착의 장단점?1. 장점: 코드의 표현력이 뛰어나 간결하게 쓰여진다.2. 단점: 공간의 복잡도가 높고 창고가 넘칠 위험이 있으며 중복 계산이 존재하고 과도한 함수 호출은 시간이 많이 소모되는 등 문제가 있다.

셋째, 어떤 문제를 귀속적으로 해결할 수 있습니까?하나의 문제는 다음 세 가지 조건을 동시에 만족시키면 귀환으로 해결할 수 있다.문제의 해는 몇 개의 자문제의 해로 분해할 수 있다.무엇이 하위 문제입니까?데이터 규모가 더 작다는 문제다.2. 문제와 하위 문제는 데이터 규모가 다른 것을 제외하고 해답의 방향이 완전히 같다.귀속 종료 조건이 존재합니다

넷째, 어떻게 귀속을 실현합니까?1. 귀속 코드가 귀속 코드를 작성하는 관건은 큰 문제를 작은 문제로 분해하는 규칙을 찾아내고 이를 바탕으로 추이 공식을 쓴 다음에 종지 조건을 추궁하고 마지막으로 추이 공식과 종지 조건을 코드로 번역하는 것이다.2. 귀환 코드는 귀환 코드에 대해 이해한다. 만약에 전체적인 귀환 과정을 똑똑히 생각하려 한다면 사실상 잘못된 사고방식에 들어갔다.그러면 귀속 코드를 어떻게 이해해야 합니까?만약 문제 A가 몇 개의 하위 문제 B, C, D로 분해될 수 있다면 하위 문제 B, C, D가 이미 해결되었다고 가정할 수 있다.그리고 당신은 문제 A와 하위 문제 B, C, D 두 층 간의 관계만 생각하면 됩니다. 하위 문제와 하위 문제, 하위 문제와 하위 문제 간의 관계를 층층이 생각할 필요가 없습니다.귀속 디테일을 차단하면 이해하기가 훨씬 간단해진다.따라서 귀속 코드를 이해하면 그것을 하나의 추이 공식으로 추상화하고 층층이 호출 관계를 생각하지 말고 인간의 뇌로 귀속의 모든 절차를 분해하려고 하지 마라.

다섯째, 흔히 볼 수 있는 문제와 해결 방안을 귀속시킨다.덤프 넘침 경계: 덤프 넘침을 피하기 위해 전역 변수를 설명할 수 있습니다.2. 반복 계산을 경계한다. 어떤 데이터 구조를 통해 이미 구한 값을 저장하여 중복 계산을 피한다.

6. 어떻게 귀속을 비귀속 코드로 바꿉니까?통괄적으로 말하면, 모든 귀속 코드는 교체 순환의 비귀속 문법으로 바꿀 수 있다.어떻게?추상적으로 추출 공식, 초기값과 경계 조건을 추상화한 다음에 교체 순환으로 실현한다.'최종 추천인

을 세 줄 코드로 어떻게 찾는지 참고하세요.

인스턴스

인스턴스

급승

def fact(n):

    if n==1:

        return 1

    return n * fact(n -1)

위쪽은 곱셈을 실현하는 귀속 함수이니 우리가 한번 해 보자.

>>> fact(1)
1
>>> fact(5)
120

어리둥절할 수도 있으니 계산 과정을 살펴보자.

===> fact(5)

===> 5 * fact(4)

===> 5 * (4 * fact(3))

===> 5 * (4 * (3 * fact(2)))

===> 5 * (4 * (3 * (2 * fact(1))))

===> 5 * (4 * (3 * (2 * 1)))

===> 5 * (4 * (3 * 2))

===> 5 * (4 * 6)

===> 5 * 24

===> 120

피보나치 수열

def fib(n):
    if n <2:
         return n
    else:
        return fib(n -1) + fib(n -2)

한노타

def hanoti(n,x1,x2,x3):
    if(n == 1):
        print('move:',x1,'-->',x3)
        return
    hanoti(n-1,x1,x3,x2)
    print('move:',x1,'-->',x3)
    hanoti(n-1,x2,x1,x3)