[자료구조] 재귀함수

 

 

🔍 재귀함수는 출력하는 구문이 어디에 위치하느냐에 따라 출력 순서가 달라진다.

public  class Solution {

    public static void main (String[] args) {    
    	DFS(3);
	}
    
    static void DFS(int n) {
    	if(n==0) return;
    	
    	DFS(n-1);
    	System.out.println(n);
    }
}

1
2
3

 

public  class Solution {

    public static void main (String[] args) {    
    	DFS(3);
	}
    
    static void DFS(int n) {
    	if(n==0) return;
    	
    	System.out.println(n);
    	DFS(n-1);
    }
}

3
2
1

 

 

🔍 재귀함수를 이용하여 숫자를 이진수로 출력

public  class Solution {

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

1011

 

 

🔍 팩토리얼

public  class Solution {

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

120

 

 

🔍 피보나치

💡 피보나치 수열 n번 째 수열의 n 항  구하기

public  class Solution {

    public static void main (String[] args) {    
    	System.out.println(DFS(10));
    	
	}
    
    static int DFS(int n) {
    	if(n==1) return 1;
    	if(n==2) return 1;
    	return DFS(n-2) + DFS(n-1);
    	
    }
}

55

 

 

💡 피보나치 수열 n 번째 수열의 n번째까지의 모든 항 구하기

✔ 방법1 ㅡ 반복문 이용

public  class Solution {

    public static void main (String[] args) {    
    	for(int n=1; n<=10; n++) {
    		System.out.print(DFS(n) + " ");;
    	}
	}
    
    static int DFS(int n) {
    	if(n==1) return 1;
    	if(n==2) return 1;
    	return DFS(n-2) + DFS(n-1);
    }
}

1 1 2 3 5 8 13 21 34 55

• for 문을 이용해서 구하는 방법이다.
• n 값이 커질 수록 출력하는데 시간이 오래 걸려서 비효율적이다.

 

✔ 방법2 ㅡ 배열 이용

public  class Solution {

	static int[] fibo;
	
    public static void main (String[] args) {    
    	int n = 10;
    	fibo = new int[n+1];
    	DFS(n);  // fibo 배열에 값을 넣기 위해 호출
    	for(int i=1; i<=n; i++) {
    		System.out.print(fibo[i] + " ");;
    	}
	}
    
    static int DFS(int n) {
    	if(n==1) return 1;
    	if(n==2) return 1;
    	return fibo[n] = DFS(n-2) + DFS(n-1);
    }
}

0 0 2 3 5 8 13 21 34 55

• 배열을 이용해서 DFS() 메서드를 한 번만 호출하여 배열에 피보나치 수열 값을 다 넣고 출력만 하도록 했다.
• 방법1 보다 더 나은 방법이다. 

 

✔ 방법3  ㅡ 메모이제이션 이용

public  class Solution {

	static int[] fibo;
	
    public static void main (String[] args) {    
    	int n = 10;
    	fibo = new int[n+1];
    	DFS(n);  // fibo 배열에 값을 넣기 위해 호출
    	for(int i=1; i<=n; i++) {
    		System.out.print(fibo[i] + " ");
    	}
	}
    
    static int DFS(int n) {
    	if(fibo[n]>0) return fibo[n];
    	if(n==1) return fibo[n] = 1;
    	if(n==2) return fibo[n] = 1;
    	return fibo[n] = DFS(n-2)+ DFS(n-1);
    }
}

• 배열을 이용하여 DFS() 메서드에서 한 번 구한 항의 값을 배열에 저장하여 계산 횟수를 줄였다.
• 메모이제이션이란, 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복을 제거하여 프로그램 속도를 올리는 기술이다.
• 피보나치 수열의 모든 항을 구하는 여러 방법 중에서 방법3이 제일 좋다.