피보나치 수열의 귀속과 교체 실현

귀속과 교체의 차이

귀속: 귀속은 함수 안에서 자신을 호출하는 것이다.귀환은 주로 두 가지 과정으로 나눌 수 있는데 그것이 바로 추이와 회귀이다.이른바 점차적인 추론이란 복잡한 문제의 해답을 원래의 문제보다 간단한 몇 가지 문제의 해답으로 추론하는 것이다.회귀는 가장 간단한 문제를 얻은 후에 점차적으로 되돌아와 순서대로 복잡한 문제의 해를 얻는 것이다.
교체: 교체는 변수의 원값을 이용하여 변수의 새로운 값을 추산하는 것이다.

피보나치 수열의 귀속과 교체 실현

반복 구현:

public class Solution {
    public int Fibonacci(int n) {
        if(n>39){
            return -1;
        }
        if(n<=0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        else{
          return  Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
}

실행 시간: 944ms 시간 복잡도 O (n)
반복 구현:

public class Solution {
    public int Fibonacci(int n) {
        int st =0;
        int nd =1;
        int sum =0;
        
        if(n>39){
            return -1;
        }
        if(n<=0){
            return 0;
        }
        if(n==1){
            return 1;
        }
       
        for(int i=2;i<=n;i++){
            sum = st + nd;
            st = nd;
            nd = sum;
        }
        return sum;
    }
}

실행 시간: 18ms, 복잡성 O(n)
해석: 운행 시간에서 우리는 이 두 단락의 프로그램 성능을 볼 수 있다.교체 방법으로 이 문제를 처리할 때, 운행 시간은 순환 횟수가 증가함에 따라 증가한다.귀속 방법으로 처리할 때 귀속은 자신의 함수를 호출하고 함수 호출은 운행 시간을 증가시킨다.귀속 방법을 사용하는 것도 장점이 하나 있는데 코드가 간결하고 읽기 쉽다는 것이다.