[알고리즘] 재귀호출(recursive call)이란?

 

'재귀호출(recursive call)'은

완전탐색을 구현할때 용이하다.

 

완전 탐색은

선형적 방식과 재귀적 방식(계층적)

으로 접근할 수 있다.

 

선형적 방식은 반복문을 돌려

 하나씩 탐색하는 방식이다.

 

재귀적 방식(계층적)은

Top에서 Bottom으로 Down하며

모든 경우의 수를 탐색하는 방식이다.

 

그렇다면

어떤 경우에 어떤 방식을

사용해야 할까?

 

 

반복문을 사용하는 경우

 

완전탐색은 반복문을 사용하여

구현할 수 있다.

 

 

 

1 ~ 10개의 원소가 있다.

 

이중 특정 조건에 부합하는

4가지 원소를 찾으려 한다. 

 

그럼 1부터 10까지 탐색을 해야하는데 

'반복문'을 사용한다고 가정해보자.

 

 

 

 

 

4가지 원소로 구성된 한 조합을 찾아야 하므로

for문의 변수는 네 개가 필요하다.

 

 

 

 

 

반복문을 사용하는 경우

 

10개의 원소 중

조건에 부합하는 4개의 원소 조합을

찾아야 하므로

 

4중 for문을 형성한다.

 

for( int i = 1; i<11; i++ ) {
	for( int j = i+1; j<11; j++) {
    		for( int k = j+1; k<11; k++){
        		for( int z = k+1; z<11; z++){
            			//....
            		}
        	 }
    	 }
}

 

 

1부터 10의 숫자는 서열이 없기에

1~10 중 4가지 원소를 추출하기 위해 

선형적으로 접근하는 방식은

 

'직관적'이고 나쁘지 않은 방식일 수 있다.

 

하지만

 

만약 데이터들이

특정 조건이나 계층이 있는 구조라면 

 

선형적 구조는 직관적이지 못하고

오히려 코드를 복잡하게 만든다.

 

 

재귀호출을 사용하는 경우

 

 

 

 

 

 

재귀호출은 함수(f(n))를 반복 호출하여 구현한다.

 

그러므로 단점도 있다.

 

함수는 호출되면 Stack에 쌓이기 때문에

 Stack Overflow가 발생할 수 있다.

 

또한

반복문에 비해 속도도 느리다.

 

그럼에도 

반복문이 아닌 재귀호출을 사용하는 이유가 있다.

 

바로,  계층 구조 때문이다. 

 

 

 

 

 

 

단순히 1~10까지 수를 탐색하는

선형적인 데이터의 탐색은 

재귀호출보다 반복문이 직관적으로 더 나을 수 있다.

 

그러나 

만약 계층을 갖는 데이터의 완전탐색의 경우 

재귀호출이 적합하다. 

 

 

 

 

 

 

원소의 조합이 단순히 2, 4, 5, 10 이 아니라

[ 회사, 총무, 총무2팀, 김서형 ]의 조합인 경우

TOP에서 Bottom으로 내려가는 탐색 방식이

 

재귀호출 방식과 직관적으로 일치한다.

 

 

 

 

 

피보나치 수열과 같이,

7부터 시작해서 TOP DOWN하며 탐색하는 경우도

이와 같다. 

 

 

 

 

 

 

개인적으로는

파일시스템의 파일들을 탐색하는 프로그램을

재귀호출로 구현한 적이 있다. 

 

계층 구조가 있는 데이터들을

탐색하는데 반복문을 사용하면

코드는 복잡해진다.

 

반복문은 선형적 탐색을 하지

계층적 탐색은 하지 않기 때문이다. 

 

 

즉, 선형적 사고가 아닌 재귀적 사고를 해야한다.

 

 

[JAVA] 백준 11729번 하노이 탑 이동 순서 : 재귀함수

 

 

하노이탑 문제는 재귀적 사고를 요하는 문제이고

이를 선형적으로로 접근하면 코드는 복잡해진다. 

 

이와 같이,

재귀호출(recursive call)은 완전탐색을 요하는 문제에서

선형적 접근이 아닌 재귀적, 계층적 접근이 필요할 때

유용한 알고리즘 방식이다.

 

 

 

 

---

 

 

 

 

참고자료

 

알고리즘 문제 해결 전략 세트

[Algorithm] 재귀와 반복문