[recursion 예제3] 매개변수의 명시화

 

순환적 알고리즘을 설계하기 위해선 2가지가 필요하다.

1. 적어도 하나의 base case(종료되는 case)가 있어야 한다.

2. 모든 case는 결국 base case로 수렴한다.

 

 

* 추가로, 

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔야한다!

 ->이번 포스팅은 명시적 매개변수로 표현하는 법에 대한 것이다.

 

 

---

"순차 탐색"을 통해  두 매개변수의 차이점과 recursion의 응용을 알아보자.

 

 

암시적 매개변수?

data[0]에서 data[n-1] 사이에서 target을 검색하는 코드이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int data[6] = { 1,2,3,4,5,6 };
	printf("%d", search(data,6,4));
}
int search(int* data, int n, int target) {
	for (int i = 0; i < n; i++)
		if (data[i] == target)
			return i;
	return -1;
}

결과:3

->하지만, 검색 구간의 시작 인덱스인 0은 보통 생략한다.즉, 암시적(implicit) 매개변수로 설정한 것이다.

---

 

명시적 매개변수?

data[begin]에서 data[end] 사이에서 target을 검색하는 코드이다.

 

순차탐색 ver.1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int data[6] = { 1,2,3,4,5,6 };
	printf("%d", search(data,0,5,4));
}
int search(int* data, int begin,int end, int target) {
	if (begin > end) //검색할 개수가 0개일 때
		return -1;
	else if (target == data[begin])
		return begin;
	else
		return search(data, begin + 1, end, target);
}

순차탐색 ver.2 (binary search와는 다름)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int data[6] = { 1,2,3,4,5,6 };
	printf("%d", search(data,0,5,4));
}
int search(int* data, int begin,int end, int target) {
	if (begin > end)
		return -1;
	else {
		int middle = (begin + end) / 2;
		if (data[middle] == target)
			return middle;
		int index = search(data, begin, middle - 1, target);
		if (index != -1)
			return index;
		else
			return search(data, middle + 1, end, target);
	}
}

 

결과:3

-> 즉, 검색구간의 시작점을 begin으로 설정해 명시적(explicit)으로 지정한다.

*자기자신을 호출할 때 혼동 방지를 위해서 시작부분을 명시하는 변수가 있어야 한다.

 

---

매개변수의 명시화를 이용해 다른 코드를 구현해보자.

최대값 찾기 ver.1

(begin <= end라고 가정하자.)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int findMax(int* data, int begin, int end);
int main(void) {
	int data[6] = { 11,102,0,2,14,33 };
	cout<<findMax(data, 0, 5)<<endl;
}
int findMax(int* data, int begin, int end) {
	if (begin == end)
		return data[begin];
	else
		return max(data[begin], findMax(data, begin + 1, end));
}

결과:102

최대값 찾기 아이디어

 

최대값 찾기 ver.2

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int findMax(int* data, int begin, int end);
int main(void) {
	int data[6] = { 11,102,0,2,14,33 };
	cout<<findMax(data, 0, 5)<<endl;
}
int findMax(int* data, int begin, int end) {
	if (begin == end)
		return data[begin];
	else {
		int middle = (begin + end) / 2;
		int max1 = findMax(data, begin, middle);
		int max2 = findMax(data, middle + 1, end);
		return max(max1, max2);
	}
}

결과:102

최대값 찾기 2  아이디어

 

---

나는 지금까지 반복문을 활용하면서 암시적 매개변수를 대부분 사용한 것 같다.

명시적 매개변수의 활용의 이점을 알았고, 앞으로를 위해서 명시적 변수를 쓰는 연습을 해둬야겠다.