반복 귀속 꼬리 귀속 효율 비교

미귀환은 귀환이 없는 귀환만 점차적으로 미루는 것이다.
나는 자바 프로그램으로 각각 교체, 귀속, 꼬리 귀속의 방식으로 피보나치 수열(45)을 실현하고 그들의 운행에 걸리는 시간을 관찰한다.

public class Test {

    public int iterator(int n) {
        if(n <= 0) {
            return 0;
        }
        int first = 1;
        int second = 1;
        int result = 1;
        for(int i = 3; i <= n; ++i) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

    public int recursion(int n) {
        if(n <= 0) {
            return 0;
        }
        if(n <= 2) {
            return 1;
        }
        return recursion(n - 1) + recursion(n - 2);
    }

    public int tailRecursion(int n, int first, int second) {
        if(n <= 0) {
            return 0;
        }
        if(n <= 2) {
            return second;
        }
        return tailRecursion(n - 1, second, first + second);
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        Test test = new Test();
        //System.out.println(test.iterator(n));
        //System.out.println(test.recursion(n));
        System.out.println(test.tailRecursion(n, 1, 1));
    }
}

교체: 0.054s
반복: 3.615s
마지막 귀속:0.057s
교체는 비귀속 시간과 거의 차이가 없다. 예전에는 책에서 교체 효율이 낮다고 했지만 어디가 낮은지 알 수 없었다. 점차적으로 추진할 때 창고를 닫아야 하고 창고는 모든 함수가 호출된 정보를 유지하고 회귀할 때까지 풀었다(출고).마지막 귀환은 회귀 과정이 없기 때문에 방대한 창고를 유지할 필요가 없고 새로 호출된 함수는 원래의 함수를 덮어씁니다.그리고 나서 나는 c언어로 다시 한 번 실현했는데, 결과는 나를 놀라게 했다.

#include 

int iterator(int n) {
    if(n <= 0) {
        return 0;
    }
    int first = 1;
    int second = 1;
    int result = 1;
    int i = 0;
    for(i = 3; i <= n; ++i) {
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

int recursion(int n) {
    if(n <= 0) {
        return 0;
    }
    if(n <= 2) {
        return 1;
    }
    return recursion(n - 1) + recursion(n - 2);
}

int tailRecursion(int n, int first, int second) {
    if(n <= 0) {
        return 0;
    }
    if(n <= 2) {
        return second;
    }
    return tailRecursion(n - 1, second, first + second);
}

int main() {
    //printf("%d
", iterator(45));
    //printf("%d
", recursion(45));
    printf("%d
", tailRecursion(45, 1, 1));
    return 0;
}

교체:0.001s
반복: 7.307s
꼬리 귀속: 0.001s c 언어의 귀속은 뜻밖에도 자바의 두 배이다. 보아하니 c가 자바보다 빠르다는 결론은 너무 독단적이어서 구체적인 상황을 구체적으로 분석해야 한다.