#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
bool subsetsum_tail(vector<int>& subset, int sum, int i) {
	if (i == subset.size()) {
		return true;
	}

	return subsetsum(subset, sum + subset[i], i + 1) || subsetsum(subset, sum, i + 1);
}
}}}
----
재귀 탐색을 루프로 구현
{{{#!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.0022s
재귀를 반복문으로 구현 -- 0.0058s