#keywords C++,재귀
교과서에 보면 모든 재귀 탐색은 루프로 구현 가능하다고 적혀 있다. 일반적으로 아래와 같이 스택으로 구현한다.

재귀가 반복문보다 메모리를 많이 차지하며 속도가 느리다고 알려져있다. 하지만 이건 언어에 따라 다르다. 그리고 컴파일러에 따라 다르다. 그리고 데이터 셋에 따라 다르다. 일반적으로 재귀 탐색을 루프로 직접 구현하는건 드라마틱하게 속도가 빨라지지 않는다. 성능만을 생각한다면 루프 구현이 아니라 컴파일러가 꼬리 재귀(tail recursion, return에서 추가 연산을 필요로 하지 않는 형태) 최적화가 가능한 형태로 재귀 탐색을 구현하는 것이 낫다(__컴파일러가 가능하면 최적화 하는 과정에서 꼬리 재귀를 반복문으로 변경한다__). 기존 재귀의 문제였던 메모리와 성능에 대한 문제가 제거되는 것이다. 루프로 직접 구현할 때 이점은 재귀 깊이가 아주 깊어질 때 스택이 깨지는 건 확실히 막을 수 있다.

재귀로 구현한 부분 집합의 모든 경우의 수 탐색
{{{#!gcode
bool subsetsum(vector<int>& subset, int sum, int i) {
	if (i == subset.size()) {
		return true;
	}

	bool append = subsetsum(subset, sum + subset[i], i + 1);
	bool ignore = subsetsum(subset, sum, i + 1);

	return append || ignore;
}
}}}
----
재귀 탐색을 루프로 구현
{{{#!gcode
void subsetsum_loop(vector<int>& subset, int sum, int i) {
	struct SnapShotStruct {
		int sum;
		int i;
		int stage;
	};

	stack<SnapShotStruct> snapshotStack;

	SnapShotStruct currentSnapshot;
	currentSnapshot.sum = 0;
	currentSnapshot.i = 0;
	currentSnapshot.stage = 0;

	snapshotStack.push(currentSnapshot);

	while (!snapshotStack.empty()) {
		currentSnapshot = snapshotStack.top();
		snapshotStack.pop();

		switch (currentSnapshot.stage)
		{
		case 0: // subsetsum(subset, sum + subset[i], i + 1);
		{
			if (currentSnapshot.i == subset.size()) {
				continue;
			}

			currentSnapshot.stage = 1;
			snapshotStack.push(currentSnapshot);

			SnapShotStruct newSnapshot;
			newSnapshot.sum = currentSnapshot.sum + subset[currentSnapshot.i];
			newSnapshot.i = currentSnapshot.i + 1;
			newSnapshot.stage = 0;

			snapshotStack.push(newSnapshot);
		}
			continue;
		case 1: // subsetsum(subset, sum, i + 1);
		{
			currentSnapshot.stage = 2;
			snapshotStack.push(currentSnapshot);

			SnapShotStruct newSnapshot;
			newSnapshot.sum = currentSnapshot.sum;
			newSnapshot.i = currentSnapshot.i + 1;
			newSnapshot.stage = 0;
			snapshotStack.push(newSnapshot);
		}
			continue;
		case 2: // return;
			continue;
		default:
			break;
		}
	}
}
}}}
----
속도 비교(Release 모드, 탐색 30,000번)
재귀로 구현한 부분 집합의 모든 경우의 수 탐색 -- 0.0046s
재귀를 반복문과 스택으로 구현 -- 0.0058s