[자료구조] 재귀(recursion), 이진탐색, 순차탐색

이소영·2023년 10월 10일

자료구조

목록 보기

3/9

재귀(recursion)

recursion이란 알고리즘이나 함수가 '자기 자신'을 호출하는 방식의 기법을 말한다. 즉 자기 자신을 호출함으로써 반복적으로 일을 수행할 수 있도록 하는 것이다.

반복적인 일을 수행하는 것은 반복문으로도 구현할 수 있는데 재귀함수는 어떤 경우에 쓰는 것일까?

반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우
문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
반복문으로 작성된 코드를 더 간결하고 쉽게 작성하고 싶은 경우

코드를 작성할 때 반복문이 계속 중첩되면 지나치게 복잡해지는 경우들이 발생한다. 이런 경우에 반복문보다 더 간결하게 구현하기 쉬운 재귀가 해결책이 될 수 있다.

재귀함수의 구현방법

base case: 재귀를 종료시키는 종결문이다. 재귀함수 호출을 탈출시키는 조건으로 구성하면 된다.
recursive case: 종결문의 조건에 도달할 때까지 자기 자신의 함수를 계속해서 호출시키는 구문이다.

재귀에서 가장 중요한 것은 탈출구문을 꼭 설정해줘야 한다는 것이다. 재귀를 종료하는 종결문의 조건이 없으면 자기 자신의 함수 호출을 멈추지 않고 무한루프에 빠지기 때문이다.

예제(factorial)

int factorial(int n) {
  if(n<=1) return 1; //base case
  return n * factorial(n-1); //recursive case
}

위의 코드는 입력값 n의 팩토리얼을 구하는 코드이다.
함수호출을 멈추는 종결문이 base case에서는 n이 1보다 작거나 같아질 때 1로 리턴하여 재귀를 멈추도록 되어있다.
재귀함수를 호출시키는 recursive case에서는 n-1의 값을 넘겨 다시금 자기 자신의 함수를 호출하며 리턴하도록 되어있다.

만약 n의 값으로 3을 받았을 경우에는 다음과 같은 과정으로 함수호출이 반복되며 실행된다.

factorial(3);
 
return 3 * factorial(2);
return 2 * factorial(1);
return 1;

n의 값이 1보다 작거나 같아 1을 리턴하기 전에는 넘겨받은 값으로 함수 본인을 다시 호출하여 실행되는 것이다.

순서를 본다면 종결문에서 1을 갖고 factorial(1)로 return,
factorial(1)은 1이므로 factorial(2)에서 2를 return,
마지막으로 factorial(3)에서 6의 값이 return되어 결과값이 되는 것이다.

이걸 반복문으로 구현하면 다음과 같다.

int factorial(int n){
   product = 1;
   for(int i = 1; i <= n; i++){
             product = product*i;
   }
   return product;
}

예제2(fibonacci)

int fibonacci(int n){
   if(n < 2)
   return n;
   return fibonacci(n-2) + fibonacci(n-1);
}

위의 코드는 피보나치 수열을 재귀함수로 구현한 것이다.
피보나치 수열에서 0과 1은 고정값이기 때문에 base case로 n<2가 true가 된다면 n으로 return하여 함수호출을 멈추도록 설정한다.

만약 n의 값으로 4가 주어졌다면

fibonacci(4) -> fibonacci(2)+fibonacci(3) 
fibonacci(3) -> fibonacci(1)+fibonacci(2) 
fibonacci(2) -> fibonacci(0)+fibonacci(1) 

fibonacci(0) -> n < 2 TRUE -> return 0;
fibonacci(1) -> n < 2 TRUE -> return 1;

fibonacci(2) -> 0 + 1 = 1
fibonacci(3) -> 1 + 1 = 2
fibonacci(4) -> 1 + 2 = 3

위의 과정으로 마지막 fibonacci(4)에서 3의 값을 return하여 결과값이 되는 것이다.

그러나 피보나치 수열은 n항을 알기 위해 n-1항과 n-2항을 같이 호출해야 하는데 이 과정에서 많은 중복이 일어난다. 특히 입력값 n의 크기가 커지면 커질수록 중복 계산이 심해져 recursion으로 구현하는 것은 비효율적이라고 할 수 있다.

피보나치 수열을 반복문으로 구현하면 다음과 같다.

int fibonacci(int n) {
    if(n < 2) return n;
    else {
        int i, tmp, current = 1, last = 0;
        for (i = 2; i <= n; i++) {
            tmp = current;
            current = current + last;
            last = tmp;
        }
        return current;
    }
}

반복문이 더 복잡해 보이지만 실제 재귀로 구현한 코드의 시간복잡도는 O(2ⁿ)
반복문의 시간복잡도는 O(n)으로 반복문으로 구현하는 것이 더 효율적이다.

이진탐색과 순차탐색

이진탐색

이진탐색(Binary Search)은 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다.

배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄이며 진행되는 방식이다.

더 구체적으로 말하자면 다음과 같다.

찾고자 하는 값을 중간 요소와 비교한다.

값이 중간 요소와 일치하면 중간 요소의 위치값을 리턴한다.

찾고자 하는 값이 중간 요소보다 크다면, 값은 중간 요소 뒤에 있는 오른쪽(큰) 절반 배열 안에만 있을 수 있다. 그리고 오른쪽 절반에서 다시 알고리즘을 적용한다.

찾고자 하는 값이 중간 요소보다 작으면, 값은 중간 요소 앖에 있는 왼쪽(아래) 절반에 위치해야 한다. 그래서 왼쪽 절반에 다시 알고리즘을 적용한다.

이진탐색은 재귀로 구현할 수도 있고 반복문을 통해 구현할 수도 있다.

먼저 찾는 값과 가운데 배열 요소를 비교하는 함수를 매크로로 생성한다.

#define COMPARE(a,b) ((a>b)?1:((a==b)?0:(-1))) //compare함수 매크로 생성

a에는 가운데 요소를 대입, b에는 찾으려는 값을 대입하면 된다.

a>b인 경우 1 => 찾고자 하는 값이 오른쪽에 없는 것이기 때문에 오른쪽을 버리고 왼쪽으로 전진
a = b인 경우 0=> 찾고자 하는 값이 가운데 요소와 일치한다는 뜻, 바로 리턴
a<b인 경우 -1 => 찾고자 하는 값이 왼쪽에 없는 것이기 때문에 왼쪽을 버리고 오른쪽으로 전진

재귀(recursion)

int binsearch(int list[ ], int searchnum, int left, int right) {
    int middle; 
	if(left<=right) //조건문 (left와 right가 교차되면 값이 안에 없었던 것)
	{
	    middle = (left+right)/2; // 중간 요소 설정 
	    switch (COMPARE(list[middle],searchnum)){
	        case -1: return binsearch(list,searchnum,(middle+1),right); //왼쪽 배열을 버리고 오른쪽 다시 탐색(함수호출)
	        case 0: return middle; // 중간 요소랑 찾고자 하는 값이 일치하면 그대로 리턴
	        case 1: return binsearch(list,searchnum,left,(middle-1)); //오른쪽 배열을 버리고 왼쪽으로 다시 탐색(함수호출)
	    }
	}
	return -1; //배열 안에 값이 없으면 -1을 return
	
}

반복(Iterative)

int binsearch(int list[ ], int searchnum, int left, int right) {
    int middle;
	while(left<=right)
	{
	    middle = (left+right)/2;
	    switch (COMPARE(list[middle],searchnum)){
	        case -1: left = middle + 1; //왼쪽 배열 버리고 오른쪽으로 전진
                     break; //case를 빠져나와 반복문으로 루프
	        case 0: return middle; //찾고자 하는 값을 찾았기 때문에 그대로 리턴
	        case 1: right = middle - 1; //오른쪽 배열 버리고 왼쪽 배열로 전진
                     break;
	    }
	}
	return -1;
	
}

순차탐색

이진탐색의 경우 데이터가 배열로 순서대로 정렬되어 있는 경우에 쓸 수 있는 탐색범위를 줄여가며 빠르게 값을 찾을 수 있는 탐색방법이다.
데이터가 무작위로 나열되어 있는 경우에는 차례대로 탐색을 진행해야 하는데 이런 경우 쓰는 것이 순차탐색이다.

순차탐색(Sequential Search)은 말그대로 찾고자 하는 값을 앞에서부터 순차적으로 하나씩 확인하며 찾는 방식이다.
순차탐색을 반복문으로 구현하면 다음과 같다.

int seqsearch(int list[ ], int searchnum, int left, int right) {
    //왼쪽에서 오른쪽으로 차례대로 이동하며 값 찾기
    for (int i = left; i <= right; i++) {
        if (list[i] == searchnum) { //배열의 요소가 찾고자 하는 값과 일치하면 배열 위치 리턴
            return i; 
        }
    }
    return -1; //찾고자 하는 값이 없으면 -1 리턴
}