[자료구조] 재귀 Recursion

1. 팩토리얼 구하기

class Factorial {
	public double getFactorial(double n) {
		if(n == 0)
			return 1;
		else
			return n * getFactorial(n-1);
	}
}

public class Recursion {

	public static void main(String[] args) {
		Factorial factorial = new Factorial();
		
		System.out.println(factorial.getFactorial(5));
	}

}

2. 최대공약수 구하기

💡 두 자연수 a, b(b > a)의 최대 공약수는 b-a와 a의 최대공약수와 같다는 점에 착안한다.

class GCD {
	public int getGCD(int a, int b) {
		if(b == 0)
			return a;
		else
			return getGCD(b-a, a);
	}
}

public class Recursion {

	public static void main(String[] args) {
		GCD gcd = new GCD();
		
		System.out.println(gcd.getGCD(8, 12));
	}

}

3. 이진 검색

class BinarySearch {
	int[] list;
	int left, right;
	
	BinarySearch(int list[]){
		this.list = list;
		this.left = 0;
		this.right = list.length-1;
	}
	
	public int getSpecified(int item) {
		int mid=0;
		if(left < right) {
			// 비교할 데이터가 남아있을 때
			mid = (left+right) / 2;
			if(item == list[mid]) 
				// 찾았을 경우 해당 위치 리턴
				return mid;
			else if(item < list[mid]) {
				// 찾고자하는 수가 중앙값보다 작다면
				right = mid-1;
				getSpecified(item);
			} else {
				left = mid+1;
				getSpecified(item);
			}
		}
		// 찾지 못했을 경우
		return -1;
	}
}

public class Recursion {

	public static void main(String[] args) {
		int[] list = { 3, 7, 8, 11, 13, 19, 25 };
		BinarySearch bs = new BinarySearch(list);
		System.out.println(bs.getSpecified(11));
	}

}

4. 하노이탑 Hanoi Tower

pole A, B, C가 있고 원판 n개가 pole A에 크기가 큰 순으로 꽂혀 있을 때, 모든 원판들을 그대로 pole C에 옮기는(단, 원판은 한번에 하나씩만 옮길 수 있다.) 대표적인 재귀함수 문제.

❗ 남는 pole 하나를 temporary라고 생각하고 문제를 풀면 된다. 즉, 다음 과정을 재귀적으로 따른다.
1. n-1 개의 원판들을 A에서 B로 옮긴다.
2. 가장 큰 원판을 A에서 C로 옮긴다.
3. n-1개의 원판들을 B에서 C로 옮긴다.

class Hanoi {
	public void startHanoi(int n, String from, String tmp, String to) {
		// n은 원판의 개수
		if(n == 1)
			System.out.println("원판" + n +"을 " + from + "에서 " + to + "로 옮긴다.");
		else {
			startHanoi(n-1, from, to, tmp);
			System.out.println("원판" + n +"을 " + from + "에서 " + to + "로 옮긴다.");
			startHanoi(n-1, tmp, from, to);
		}
	}
}

public class Recursion {

	public static void main(String[] args) {
		Hanoi hanoi = new Hanoi();
		hanoi.startHanoi(3, "A", "B", "C");
	}

}

5. 순열 Permutation

n개의 요소로 가능한 모든 순열 구하기

💡 a, b, c 세 개의 요소가 있을 때 a를 고정하고 부분범위 {b, c}끼리 자리를 바꾼다. 이 과정을 재귀적으로 반복.

class Permutation {
	String list[];
	
	Permutation(String list[]){
		this.list = list;
	}
	
	public void perm(int start, int end) {
		int i;
		if(start == end) {
			for(i=0; i<=end; i++) 
				System.out.print(list[i]);
			System.out.println();
		}else {
			for(i=start; i<=end; i++) {
				swap(start, i);	// 고정시킬 요소 바꿔주기
				perm(start+1, end);	// 부분범위끼리 자리바꾸기
				swap(start, i);	// 고정요소 다시 원위치
			}
		}
	}
	
	public void swap(int i, int j) {
		String tmp;
		
		tmp = list[i];
		list[i] = list[j];
		list[j] = tmp;
	}
}

public class Recursion {

	public static void main(String[] args) {
		String list[] = {"a", "b", "c"};
		Permutation permutation = new Permutation(list);
		permutation.perm(0, 2);
	}

}