C Data Structure - 재귀를 통한 이진탐색 구현해보기

지난 포스팅 때, 재귀는 믿음이 졸라 중요하다고 했다. 이번에도 마찬가지다.

그 전에 재귀를 공부할 때, 써야하는 경우에 대한 추가적인 기록이 필요할 것 같아서 먼저 기록한다.

재귀가 필요한 경우

재귀가 필요한 경우는 다음과 같다.

탈출 조건이 명확하고, 같은 작업이 계속해서 반복되는 경우.

피보나찌 수열에서는 n-2항과 n-1 항이 더해지는 부분이 반복된다.

Fibonacci(5) 이면 Fibonacci(4) + Fibonacci(3) 인데 Fibonacci(4)에도 Fibonacci(3)에도 n-2항과 n-1항이 더해지는 부분이 필요하기 때문에 반복이 되고, 이를 재귀로 구현했던 것이다.

이번 포스팅에서 구현해 볼 이진 탐색에서 또한 마찬가지다. 

가운데 값을 구한 후 비교 -> 범위 재설정 

이 작업이 반복되기 때문이다. 탈출 조건의 명확성은 말할 것도 없고 말이다.

이진 탐색에서도 믿음이 필요한가?

물론이다. 필요하다. 위에서 제시한 재귀가 필요한 경우와 믿음이 존재한다면 재귀 함수를 마음 놓고 신경도 안 쓰고 사용해도 된다.