[알고리즘]_순환(Recursion)_2 순환의 적용

부경대학교 권오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘'

---

 

Recursion의 적용

---

• 문자열의 길이 계산

문자열이 비어있으면 문자열의 길이는 0,

그렇지 않으면 1+(문자열의 첫 번째 문자를 제외한 문자열의 길이)이다.

public static int length(String str) {
	if(str.equals("")) 
		return 0; 
	else
		return 1+length(str.substring(1)); // 1+(문자열의 첫 번째 문자 제외한 문자열의 길이)
}

 

---

 

• 순차 탐색

data[0]에서 data[n-1] 사이에서 target을 검색한다.

target이 존재하면 배열의 인덱스를 반환하고, 존재하지 않으면 -1을 반환한다.

public int search(int data[], int n, int target) {
	if(n<=0)
		return -1;
	else if(target == data[n-1])
		return n-1;
	else
		return search(data, n-1, target);
	}

인덱스가 큰 것부터 내려옴

 

 

---

 

• 2진수로 변환하여 출력

음이 아닌 정수를 2진수로 변환한다.

정수 n이 0이나 1이면 그냥 2진수이므로 n을 출력하면 되고,

n이 2이상의 정수이면 n을 2로 나눈 몫을 먼저 2진수로 출력한 후,

n을 2로 나눈 나머지를 2진수로 출력한다.

public void printInBinary(int n) {
	if(n<=1)
		System.out.println(n);
	else {
		printInBinary(n/2); 
		System.out.println(n%2);
	}
}

 

 

---

 

 

• Disjoint Sets(Union find): 서로소 집합

Disjoint Sets는 서로 중복되지 않는 원소들로 이루어진 집합들이다.

즉 집합들 간에 교집합이 없다.

배열 A는 m개의 원소들로, 배열 B는 n개의 원소들로 정렬되어 있다.

public boolean isDisjoint(int m, int A[], int n, int B[]) {
	if(m<0 || n<0)
		return true;
	else if(A[m-1]==B[n-1])
		return false;
	else if(A[m-1]>B[n-1])
		return isDisjoint(m-1, A, n, B);
	else
		return isDisjoint(m, A, n-1, B);
	}