[C/C++ 8.3] 알고리즘 - 재귀

 

재귀(recursion);

자기자신(함수)를 
반복해서 호출함으로써
반복문의 기능을 대체하고,
break point를 자유롭게 설정함

경우의 수 / 순열 / DFS / BFS 
로 응용할 수 있다.

---

재귀사용

기본

//Level 20			

//1번
void bbq(int cnt) {
	if (cnt >= 5)
		return;
	bbq(cnt + 1);
}
int main() {
	bbq(0);
	return 0;
}

 

// Level 21
//3번
void recur(int level, int branch, int LV) {	// level, branch는 입력받은 값  //LV 은 현재 상황
	if (LV == level)					// level은 트리의 깊이 (몇번이나 재귀 안으로 깊숙히 들어가는가)
		return;							// branch는 가지의 개수 (재귀가 몇번이나 반복되는가 )
	for (int i = 0; i < branch; i++)	// 레벨과 브랜치 확실히 정리 !!!!!! ****************************************
		recur(level,branch,LV + 1);
}
int main() {
	int level, branch;
	cin >> level >> branch;
	recur(level,branch,0);
}

 

// Level 20

//2번
void countdown(int a) {		//int로 함수 설정하면 error남 !! return 을 선택적으로 하기 때문 ! **********************
	cout << a << " ";		//1 번) 순차 출력 위치
	if (a == 0)
		return;
	countdown(a - 1);
	cout << a << " ";		// 2번) 역순 출력 위치
							// 여기에 cout을 추가함으로써, return이 함수호출한 곳으로 되돌아가 다시 4,3,2,1,0,1,2,3,4 이렇게 재 출력됨
}
int main()
{
	int a;
	cin >> a;
	countdown(a);
	return 0;
}

//4번
void abc(int a, int cnt) {
	if (cnt > 3)
		return;
	abc(a + 2, cnt + 1);	//재귀 호출 이전에는 cout이 없으므로 출력 안되다가,
	cout << a << " ";		//return 후, cout이 있으므로 여태 거쳐온 변수값 역순으로 출력됨
}
int main() {
	int cnt = 0;
	int input;
	cin >> input;
	abc(input, cnt);
	return 0;
}

 

* //int로 함수 설정하면 error남 !! return 을 선택적으로 하기 때문 ! **********************

 

* 문자열 재귀출력시 주의 

//5번
void prt(char arr[6], int idx) {
							// 여기에 1번 순차출력을 둘 경우, index[5] 즉, null문자를 출력하려 하기 때문에 틀림 !!
							// 이 위치는 단순 숫자 출력이면 error 안뜨지만, 배열(특히 문자열 ) 일 경우. 범위에서 벗어난 index를
							// 출력하려 하기 때문에 이왕이면 if 안으로 다 넣어서 써주는게 좋음

	if (idx > 4) {			// 이 if - return 문을 1번의 위에두냐, 아래에 두냐에 따라서
		// 줄바꿈 기회 여기밖에 없음 !!
		cout << endl;		//  i) 마지막 index를 한번만 출력하냐(찍고 돌아감)
		return;				// ii) 정순, 역순 일때 나란히 한번씩 두번 출력하냐 (한텀쉬고, 다시 거기부터 시작)
	}						//     을 구분할 수 있음
	cout << arr[idx];		// 1번 순차출력 위치
	prt(arr, idx + 1);
	cout << arr[idx];		// 2번 역순출력 위치
}
int main() {
	char arr[6];
	cin >> arr;
	prt(arr,0);
	return 0;
}

 

 

거꾸로 -1 씩 재귀호출하기

//7번
void recur(int arr[8],int a) {
	if (a == 0) {
		cout << arr[a] << " ";
		return;
	}
	cout <<arr[a] << " ";
	recur(arr,a - 1);
	cout << arr[a] << " ";
}
int main() {
	int a;
	int arr[8] = { 3,7,4,1,9,4,6,2 };
	cin >> a;
	recur(arr,a);
	return 0;
}