재귀


어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될때 재귀적(recursive)이라고 한다.


1은 자연수, 

자연수 n의 바로 다음수도 자연수


재귀적 정의에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의할수 있다.

재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 할 수 있다.



1. 재귀 메소드 사용, 미사용 팩토리얼 값 구하기



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package myTest2;
 
import java.util.Scanner;
 
public class Factorial {
    // 팩토리얼을 재귀적으로 구현
    // 재귀 메서드를 사용하여 양의 정수 n의 팩토리얼을 반환한다.
    static int factorial(int n){
        if(n>0return n * factorial(n-1);
        else return 1;
    }
    
    // 자기 자신을 부르지 않고 구현한 메서드
    static int notUsingRecursive(int n){
        if(n>0){
            int value = 1;
            for(int i=n; i>0; i--){ 
                value = value * i; 
            }
            return value;
        }else{
            return 1;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("정수를 입력하세요: ");
        int x = scanner.nextInt();
        System.out.println(x+ "의 팩토리얼은 " + factorial(x) + "입니다.");
        System.out.println(x+ "의 재귀메서드 사용안한 메서드는 " + notUsingRecursive(x) + "입니다.");
    }
}
cs


결과



2. 유클리드 호제법을 사용하여 두 정수의 최대공약수를 재귀적으로 구하는 방법



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package myTest2;
 
import java.util.Scanner;
 
public class EuclidGCD {
    // 재귀를 사용하여 정수 x,y 의 최대공약수 반환
    static int gcd(int x, int y){ 
        if(y == 0return x;
        else return gcd(y, x%y);
    }
    
    // 재귀를 사용하지 않고 정수 x,y 의 최대공약수 반환
    static int notUsingRecursive(int x, int y){
        if(y == 0) {
            return x;
        }else { 
            int value1 = y; 
            int value2 = y ;
            y = x % y;    
            while(y!=0){
                value2 = y; 
                y = value1 % value2; 
                value1 = value2;
            }
            return value2;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("두 정수의 최대공약수를 구합니다.");
        System.out.print("정수를 입력하세요 : ");    int x = scanner.nextInt();
        System.out.print("정수를 입력하세요 : ");    int y = scanner.nextInt();
 
        System.out.println("최대공약수는" + gcd(x,y) + "입니다.");
        System.out.println("최대공약수는" + notUsingRecursive(x,y) + "입니다.");
    }
}
cs


재귀를 사용하지 않고 정수 x,y 의 최대공약수 반환메소드, 재귀를 사용한 메소드를 구현하였다.


결과



3. 재귀를 사용한 하노이의 탑 구현



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package myTest2;
 
import java.util.Scanner;
 
public class Hanoi {
    
    // 재귀함수
    static void move(int no, int x, int y){
        
        if(no > 1){
            move(no-1, x, 6-x-y);
        }
        
        String stringX = "";
        String stringY = "";
        if(x==1) stringX = "A";
        if(y==1) stringY = "A";
        if(x==2) stringX = "B";
        if(y==2) stringY = "B";
        if(x==3) stringX = "C";
        if(y==3) stringY = "C";
        
        System.out.println("원반[" + no + "]을" + stringX + "기둥에서 " + stringY + "기둥으로 옮김");
        if(no > 1){
            move(no-16- x-y, y);
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("하노이의 탑");
        System.out.println("원반 개수 : ");
        int n = scanner.nextInt();
        move(n, 13);    // 1번 기둥의 n개의 원반을 3번 기둥으로 옮김
    }
}
cs


결과




소스 코드


myTest1.zip




+ Recent posts