[알고리즘]_순환(Recursion)_3 반복문(Iteration)과 비교

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

---

Recursion vs. Iteration

• 모든 순환 함수는 반복문(iterator)으로 변경 가능

• 모든 반복문은 순환 함수로 변경 가능

• 순환함수는 복잡한 알고리즘을 단순하게 표현하는 것이 가능하지만,

• 함수 호출에 따른 오버해드가 있다. (매개변수 전달, 액티베이션 프레임 생성 등)

 

순환적 알고리즘 설계

• 암시적 매개변수(시작 지점을 암시적으로 0부터라고 하는 것)에서

• 명시적 매개변수(시작과 끝을 정확히 나타내는 것)로 바꾸어라

---

 

이진 탐색: Iterator(반복문 버전)

public int binarySearch(int data[], int n, int target) {
	int begin = 0, end = n - 1; // 시작과 끝 명시
	while(begin<=end) { // 시작이 끝보다 작거나 같을 동안
		int middle = (begin+end) / 2; 
		if(data[middle] == target) // 중간의 값과 타겟이 같으면
			return middle; // 중간 인덱스를 리턴
		else if(data[middle] > target) // 중간의 값이 타겟보다 크면 
			end = middle - 1; // 끝은 중간에서 하나 작은 인덱스가 된다.
		else // 중간의 값보다 타겟이 더 크면
			begin = middle + 1; // 시작 지점이 중간에서 하나 큰 인덱스가 된다.
	}
	return -1;
}

 

 

---

 

이진 탐색: Recursive 버전

public int binarySearch(int data[], int target, int begin, int end) {
	if(begin > end)
		return -1;
	else {
		int middle = (begin+end)/2;
		if(data[middle] == target)
			return middle;
		else if(data[middle]>target)
			return binarySearch(data, target, begin, middle-1); // begin부터 middle-1까지 다시
		elsㅁAe
			return binarySearch(data, target, middle+1, end); // middle+1부터 end까지 다시
	}
}

 

 

---

 

2-SUM: Iterator(반복문 버전)

배열의 데이터는 오름차순으로 정렬되어 있다고 가정한다.

public boolean twoSum(int data[], int n, int K) {
	int begin = 0, end = n-1;
	while(begin <= end) {
		if(data[begin] + data[end] == K) 
			return true;
		else if(data[begin] + data[end] < K) // 인덱스 end에 있는 값이 가장 큰데도 K보다 작으므로 
			begin++; // begin을 증가시켜야 한다.
		else // 인덱스 begin에 있는 값이 가장 작은데도 K보다 크므로 
			end--; // end를 줄여야 한다.
	}
	return false;
}

 

---

 

2-SUM: Recursive 버전

배열의 데이터는 오름차순으로 정렬되어 있다고 가정한다.

public boolean twoSum(int data[], int begin, int end, int K) {
	if(begin>=end)
		return false;
	else {
		if(data[begin] + data[end] == K)
			return true;
		else if(data[begin] + data[end] < K) // 인덱스 end에 있는 값이 가장 큰데도 K보다 작으므로 
			return twoSum(data, begin+1, end, K); // begin을 증가시켜야 한다.
		else // 인덱스 begin에 있는 값이 가장 작은데도 K보다 크므로 
			return twoSum(data, begin, end-1, K); // end를 줄여야 한다.
	}
}