🤶 재귀함수

👶 재귀함수 예제코드

package algolecture;

public class Main53 {
    public void DFS(int n){
        if(n == 0)
            // void 형에서 return; 하면 종료의 의미도 가지고 있다.
            // 재귀함수는 stack Frame을 사용한다.
            return;
        else{
            DFS(n-1);
            System.out.print(n+" ");
        }
    }

    public static void main(String[] args) {
        Main53 T = new Main53();
        T.DFS(3);
    }
}

👶 재귀함수는 어떻게 돌아 갈까

위와 같은 방법으로 반복이 된다!

👶 이진수 출력하기

package algolecture;
public class Main54{
    public void DFS(int n){
        if(n==0)
            return;
        else{
            DFS(n/2);
            System.out.print(n%2+" ");
        }
    }
    public static void main(String[] args) {
        Main54 T = new Main54();
        T.DFS(11);
    }
}

👶 팩토리얼 예제

package algolecture;

public class Main55 {

    public int DFS(int n){
        if(n==1)
            return 1;
        else return n*DFS(n-1);
    }
    public static void main(String[] args) {
        Main55 T = new Main55();
        System.out.println(T.DFS(5));
    }
}

👶 피보나치수열 예제

class Main{
	public int DFS(int n){
    	if(n==1) return 1;
        else if(n==2) return 1;
        else return DFS(n-2) + DFS(n-1);
    }
   
  
    public static void main(String[] args){
    	Main T = new Main();
        int n = 45;
        for(int i=1;i<=n;i++)
        System.out.println(T.DFS(i) + " ");
    }
}

📢 위의 코드의 문제점

입력 숫자가 작을때는 시간복잡도가 복잡하지는 않지만, 숫자가 커질 수록 계산할수록 중복되어 호출되는 계산이 많아진다는 것이다.

수정 해보자!

package algolecture;

public class Main56 {
    static int [] fibo;
    public int DFS(int n){
        if(n==1)
            return fibo[n]=1;
        else if(n==2)
            return fibo[n]=1;
        else
            return fibo[n] = DFS(n-2)+DFS(n-1);
    }

    public static void main(String[] args) {
        Main56 T = new Main56();
        int n = 45;
        // n+1 을 하는 이유는 첫번째 index에 배열의 첫번째가 오도록 하기 위해 설정을 했기 때문이다!
        fibo = new int[n+1];
        T.DFS(n);
        for(int i=0;i<=n;i++)
            System.out.print(fibo[i] + " ");
    }

}

배열을 따로 설정을 한 후, 값을 바로 넣어준다면 값을 불러올 때, 시간을 줄일 수 있다.

위와 같은 결과를 얻는데, 7-8초가 걸렸다.

📢 더 좋은 방법은?

메모제이션을 이용하자!

if(fibo[n] > 0)
	return fibo[n];

위의 코드를 입력하면 아래와 같이 처리가 된다.

위와 같이, DFS(9)를 호출하는데 왼쪽에 DFS(8)값과 DFS(7)의 값이 이미 존재하므로, 재귀함수를 이용하지 않고, 값을 그냥 더해줌으로써, 결과를 빠르게 출력할 수 있다.

package algolecture;

public class Main56 {
    static int [] fibo;
    public int DFS(int n) {

        if (fibo[n] > 0)
            return fibo[n];
            if (n == 1)
                return fibo[n] = 1;
            else if (n == 2)
                return fibo[n] = 1;
            else
                return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }
    public static void main(String[] args) {
        Main56 T = new Main56();
        int n = 45;
        // n+1 을 하는 이유는 첫번째 index에 배열의 첫번째가 오도록 하기 위해 설정을 했기 때문이다!
        fibo = new int[n+1];
        T.DFS(n);
        for(int i=0;i<=n;i++)
            System.out.print(fibo[i] + " ");
    }

}