C++/재귀 탐색을 루프로 구현

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

재귀로 구현한 부분 집합의 모든 경우의 수 탐색

재귀 탐색을 루프로 구현

속도 비교(Release 모드, 탐색 30,000번)
재귀로 구현한 부분 집합의 모든 경우의 수 탐색 -- 0.0046s
재귀를 반복문으로 구현 -- 0.0058s


이 글에는 0 개의 댓글이 있습니다.