재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현

재귀

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

1은 자연수, 

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

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

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

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

package myTest2;
 
import java.util.Scanner;
 
public class Factorial {
    // 팩토리얼을 재귀적으로 구현
    // 재귀 메서드를 사용하여 양의 정수 n의 팩토리얼을 반환한다.
    static int factorial(int n){
        if(n>0) return 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) + "입니다.");
    }
}

결과

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

package myTest2;
 
import java.util.Scanner;
 
public class EuclidGCD {
    // 재귀를 사용하여 정수 x,y 의 최대공약수 반환
    static int gcd(int x, int y){ 
        if(y == 0) return 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) + "입니다.");
    }
}

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

결과

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

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-1, 6- 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, 1, 3);    // 1번 기둥의 n개의 원반을 3번 기둥으로 옮김
    }
}

결과

소스 코드

myTest1.zip