헛된 생각. 귀속. - 하.

반복
먼저 귀속, 교체와 순환의 의미를 말해 보시오

귀속(recursion): 함수가 끊임없이 자신을 호출하는 행위를 가리킨다

순환(loop): 조건을 충족시킨 상황에서 같은 코드를 반복적으로 집행하는 과정을 말한다

교체(iterate): 어떤 순서에 따라 하나하나 방문하는 방법

함수 호출이 존재할 때의 저장 현장에 귀속되기 때문에 창고에 들어가고 창고에 나가는 작업은 효율이 매우 낮기 때문에 이 문제의 규모가 확실하지 않을 때 용납하기 어렵다는 것을 우리는 모두 알고 있다.
그래서 우리는 귀속 알고리즘을 쓸 때 귀속을 순환 알고리즘으로 전환해야 하는 경우가 많다. 이런 전환은 서로 다른 문제에 따라 구체적으로 분석해야 하고 심지어 많은 경우에 많은 기교가 필요하다.그러나 이러한 전환은 불규칙한 것이 아니다. 우리는 귀환이 순환으로 전환되는 대체적인 방향을 정리한다.

귀속 중의 중요한 국부 변수를 저장하기 위해 자신의 창고를 구축한다.귀속 알고리즘에서 이러한 국부 변수는 시스템이 자동으로 우리를 위해 저장한 것이다.그래서 일반적으로 귀속 알고리즘에서 변환된 순환 알고리즘은 모두 창고에 사용해야 한다.두 갈래 나무의 두루 훑어보는 것은 매우 좋은 증명이다.

순환 구조를 추상화하여 귀속에 대한 호출을 순환 처리로 전환한다.이 중에서 가장 흔히 볼 수 있는 것은 돌아가는 걸음걸이 표현식으로 순환 구조에서 순환의 집행을 제어하는 데 사용된다.

귀환과 순환을 말하고 교체를 말해 봅시다.교체도 컴퓨터가 문제를 해결하는 기본적인 방법이다. 컴퓨터가 중복적인 조작에 적합한 특성을 이용하여 컴퓨터가 한 조의 지령을 중복적으로 집행하게 하고 매번 집행할 때마다 변수의 기존 값에서 새로운 값을 내놓는다.가장 흔히 볼 수 있는 것은 i*=n 또는 i+=n이다.
우리는 교체를 사용할 때 일반적으로 세 가지 주의해야 할 점이 있다.

교체 변수의 확정.교체 알고리즘에서 최소한 하나의 변수가 매번 교체 과정에서 직접 또는 간접적으로 새로운 값으로 낡은 값을 업데이트할 수 있다.

교체 관계의 확정.교체 알고리즘에서 어떤 절차를 거쳐 새로운 값을 얻어내고 낡은 값을 갱신하는가.

교체 종지 조건의 확정.만약 종지 조건이 없다면, 교체는 무한히 진행될 것이다.

일반적으로 매우 고전적인 문제들이 있는데, 교체해서 해결할 수 있다.예를 들면 계단을 오르는 문제.한 단계의 계단은 모두 20단계로 한 걸음에 1단계 또는 2단계만 올라갈 수 있도록 규정되어 있다. 그러면 이 20단계의 계단을 올라가야 한다. 총 몇 개의 총 걸음걸이가 있는지.
다음은 각각 귀속과 교체의 해법으로 이 문제를 해결한다
역귀해법
기본 사상은 바로 20단계를 올라가려면 19단계나 18단계를 올라가야 한다. 19단계부터 20단계까지는 하나의 주법이 있고 18단계부터 20단계까지는 두 가지 주법이 있다. 그러나 한 가지 주법은 먼저 19단계부터 20단계까지 올라가야 한다. 이런 주법은 19단계부터 20단계까지의 주법에 포함된다. 18단계부터 20단계까지도 하나의 주법이 있다. 순서대로 유추하면 귀속의 해법을 알 수 있다.

    // 
    public static int stepCount(int N){
        if(N == 1){
            return 1;
        }else if(N == 2){
            return 2;
        }else{
            return stepCount(N-1)+stepCount(N-2);
        }
    }

그럼 우리 이어서 교체된 해법을 봅시다.교체의 절차에 따라 교체 변수를 확정하고 이 문제에서 N계단을 오르는 걸음수 steps이다.다음에 교체 관계를 확정하면 steps(N)=steps(N-1)+steps(N-2)이다.이때부터 우리는 N-1단계 계단의 걸음수와 N-2단계 계단의 걸음수를 기록하는 두 가지 변수가 있음을 알 수 있다.교체의 종지 조건은 N으로 순환하기 때문에 우리는 교체의 해법을 얻을 수 있다
반복 해법

    public static int stepCountIterator(int N){
        int steps = 0;
        int stepsN1 = 1;
        int stepsN2 = 0;
        for(int i = 1;i<=N;i++){
            steps = stepsN1+stepsN2;
            stepsN2 = stepsN1;
            stepsN1 = steps;
        }
        return steps;
    }

귀속
우리는 귀속 효율이 매우 낮다는 것을 안다. 예를 들어 피보나치 수열f(n)=f(n-1)+f(n-2), 계산f(n)을 할 때f(n-1)와f(n-2), 계산f(n-1)을 할 때f(n-2)와 계산f(n-3)을 해야 한다. 이렇게 하면 계산f(n)을 할 때 두 번f(n-2)을 계산해야 하기 때문에 불필요한 낭비를 초래한다.
귀속은 시스템이 자동으로 국부 변수를 저장하기 때문에 만약에 우리가 수동으로 이 국부 변수를 저장하고 귀속이 시작될 때 이 변수를 귀속 방법에 전달한다면 컴파일러에게 이 과정을 최적화할 수 있다(그리고 절대 부분의 컴파일러가 이 과정에 최적화를 했다). 이렇게 귀속 호출의 결과는 바로 귀환할 수 있다.이렇게 하면'선형 귀속'을'선형 교체'로 전환시켜 효율을 크게 향상시킨다.아니면 피보나치 수열의 수열을 예로 들면 우리는 어떻게 전환해야 합니까? 피보나치 수열은 지난번과 지난번의 합을 계산해야 하기 때문에 이 두 개의 매개 변수를 늘려서 이 두 개의 값을 저장해야 하고, 동시에 실행 횟수를 저장하는 매개 변수를 늘려야 합니다.개선된 피보나치의 계산 과정은 다음과 같다.

    public static int fib(int n, int a1, int a2, intc){
        // a1 a2 
        if（n<=2）return 1；
        else{
            if(n==c) return a1+a2;
            else{
                return fib(n,a2,a1+a2,c+1);
            }
        }
    }

이것이 바로 꼬리로 돌아가는 피보나치 수열을 채택한 알고리즘으로 그의 효율은 이미 순환과 같다.
위키백과에서 꼬리 귀속에 대한 정의를 봅시다.
꼬리 귀속은 프로그래밍 기교의 하나로 귀속 함수는 일부 함수가 내부에서 자신을 호출하는 것을 가리킨다. 만약에 귀속 호출의 결과가 항상 직접 귀속되면 꼬리 귀속이 된다.끝부분 귀속은 컴파일러의 측면에서 볼 때 일반 순환으로 최적화되기 쉽다. 왜냐하면 컴퓨터는 함수 호출의 매개 변수를 다시 한 번 호출하기만 하면 기존의 창고를 복용할 수 있고 새로운 대전 공간을 다시 열 필요가 없기 때문이다.미귀환의 주요 목적은 최적화이다.
귀속 방법은 형식적으로 말하자면 귀속 방법은 방법의 최후에 있다.그리고 컴파일러의 최적화로 인해 꼬리 귀속은 창고가 넘치는 문제를 일으키지 않는다.
그리고 위에서 알 수 있듯이 꼬리 귀속의 핵심 사상은'창고에 저장해야 하는 상태를 매개 변수로 바꾸어 다음 호출에 전달하는 것'이다.