재귀 호출과 완전 탐색

1. 무식하게 풀기

공부를 할수록 우아한 답안을 만들고 싶은 마음이 커진다. 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽다.

 

이런 실수를 방지하기 위해서 '무식하게 풀 수 있을까?' 라는 생각을 해보아야한다.

 

"brute-force(무식하게 푼다)"

컴퓨터의 빠른 계산 능력을 이용해, 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법을 의미한다.

이런 알고리즘을 완전 탐색(exhaustive search)라고 한다.

 

 

2. 재귀 호출과 완전 탐색

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각으로 나눌 수 있다.

범위가 작아지면 작아질 수록 각 조각의 형태들은 유사해진다.

이러한 작업을 구현할 때 유용하게 재귀 함수(recursive function)/재귀 호출(recursion)을 사용한다.

 

재귀함수란,

자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

 

아래는 재귀 호출을 통해 1부터 n까지의 합을 구하는 함수다.

int recursiveSum(int n){
	if(n==1) return 1;
    return n + recursiveSum(n-1);
}

 

모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함한다.

이런 쪼개지지 않는, 최소한의 가장 작은 작업들을 재귀 호출의 기저 사례(base case)라고 부른다.

 

위 예제에서는 if(n==1) return 1; 이 기저 사례가 될 것이다.

 

문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해준다.