[Java] 재귀 알고리즘

Do it! 자료구조와 함께 배우는 알고리즘 입문 읽고 정리

 

5-1 재귀의 기본

재귀란?

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

 

팩토리얼 구하기

- 재귀의 사용 예: 팩토리얼

class Factorial {
	// 양의 정수 n의 팩토리얼을 반환
    static int factorial(int n) {
    	if (n > 0) return n * factorial(n-1);
        else return 1;
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        
        System.out.println(x+ "의 Factorial은 " + factorial(x));
    }
}

 

유클리드 호제법

- 두 정수의 최대공약수를 재귀적으로 구하는 방법

class EuclidGCD {
	// 정수 x, y의 최대공약수를 구하여 반환
    static int gcd(int x, int y) {
    	if (y ==0) return x;
        else return gcd(y, x%y);
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        System.out.println("최대 공약수는 " + gcd(x, y));
    }
}

 

- 연습문제

Q1 재귀 메소드 호출을 사용하지 않고 factorial 메소드 작성

class Factorial {
	// 양의 정수 n의 팩토리얼을 반환
    static int factorial(int n) {
        int fact = 1;
		while (n > 1)
			fact *= n--;
		return (fact);
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        
        System.out.println(x+ "의 Factorial은 " + factorial(x));
    }
}

Q2 재귀 메소드 호출을 사용하지 않고 gcd 메소드 작성

class EuclidGCD {
	// 정수 x, y의 최대공약수를 구하여 반환
    static int gcd(int x, int y) {
    	while (y != 0) {
			int temp = y;
			y = x % y;
			x = temp;
		}
		return (x);
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        System.out.println("최대 공약수는 " + gcd(x, y));
    }
}

 

5-2 재귀 알고리즘 분석

 

5- 3 하노이의 탑

하노이의 탑

class Hanoi {
	// n개의 원반을 x번 기둥에서 y번 기둥으로 옮김
    static void move(int n, int x, int y) {
    	if (n > 1) move(n-1, x, 6-x-y);
        System.out.println("원반 ["+n+"]을 "+x+"기둥에서 "+y+"기둥으로 옮김");
        
        if (n > 1) move(n-1, 6-x-y, y);
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 원반 개수
        
        move(n, 1, 3); // 1번 기둥의 n개의 원반을 3번 기둥으로 옮김
    }
}