완전 탐색- 재귀함수를 이용한 완전 탐색(기본 개념)

완전 탐색은, 말그대로 어떠한 답을 도출하기 위해 가능한 모든 케이스를 연산(완전탐색)하고 확인하여 답을 도출하는 알고리즘이다. 그러므로, 완탐의 시간복잡도는 아래와 같다.

완전탐색의 시간복잡도: 가능한 모든 경우의 수 

이러한 완전탐색 알고리즘을 재귀함수를 통해 구현할 수 있다. 

재귀함수는 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다. ( 사실 알고리즘 문제풀이에 익숙하지 않으면, 자기 자신을 호출해 실행한다는 개념이 한 번에 받아들여지지는 않는다.. 인내를 갖고 반복해서 생각하는 것이 중요한 것 같다.)

재귀 함수는 Recursive Case, Base Case 두 가지로 크게 구성해서 설계하면 된다. 여기서 신기한 부분은 재귀함수는 Tree라는 자료구조로 표현이 가능하다는 점이다. 

1. Tree의 Leaf부분( 여기서의 Leaf 는 해당 Leaf Node를 기준으로 더 이상 ChildNode가 없을 때를 의미한다.) ->Base Case

2. Tree의 특정 한 부분 -> Recursive Case 로 생각할 수 있다. 

이를 Fibonacci Function을 의미하는 fib(n)으로 생각하면 아래 그림과 같다. fib(6)을 호출하면, 규칙에 따라 fib(6)의 자식노드인 fib(4), fib(5)가 호출될 것이고, 결국 더 이상 자식노드가 없는 Leaf부분인 fib(1), fib(2)까지 호출하게 되면, Base Case로 도달했기 때문에 사전에 정의한 Base Case에 대한 값을 리턴해 준다. (Recursive한 것을 Base Case를 만나면 탈출한다고 이해하자.)