재귀에 대하여

나는 재귀를 잘 사용하지 않는다.

함수 호출하는 코스트가 큰 탓도 있고,

무엇보다도 반복문으로 간단하게 표현 가능한 로직을 굳이 재귀로 표현할 필요를 못 느끼기 때문이기도 하다.

 

6주차 과제에서, 나는 min, max, sum을 재귀로 짜라는 걸 무시하고 반복문으로 짰다가 점수를 와장창 깎아먹었다.

재귀로 안짜서 그렇다고. 그래서 재귀로 다시 짜서 제출했다.

 

객체 내의 배열에서 최솟값, 최댓값, 총합계를 구하는 건 매우 쉬운 문제다.

int min(Object* self) {
    int _min = self->arr[0];
    
    for (int i = 1; i < self->size; ++i) {
        if (_min > self->arr[i]) _min = self->arr[i];
    }
    
    return _min;
}

int max(Object* self) {
    int _max = self->arr[0];
    
    for (int i = 1; i < self->size; ++i) {
        if (_min < self->arr[i]) _max = self->arr[i];
    }
    
    return _max;
}

int sum(Object* self) {
    int _sum = self->arr[0];
    
    for (int i = 1; i < self->size; ++i) {
        sum += self->arr[i];
    }
    
    return _sum;
}

 

반복문으로 짜면 이렇듯 직관적으로 간단하게 짤 수 있다.

하지만 재귀로 짜보니 이게 좀 더 직관적인거 같기도 하다.

 

// 최솟값 재귀 알고리즘
int min_rec(Object* self, int left, int right) {
    if (left > right) return MAX_VALUE; // 최댓값 리턴
    
    // 재귀적으로 left 이후의 최솟값 가져오기
    int _minval = min_rec(self, left + 1, right); 
    return self->arr[left] < _minval ? self->arr[left] : _minval;
}

int min(Object* self) {
    return min_rec(self, 0, self->size);
}

// 최댓값 재귀 알고리즘
int max_rec(Object* self, int left, int right) {
    if (left > right) return MIN_VALUE; // 최솟값 리턴
    
    // 재귀적으로 left 이후의 최댓값 가져오기
    int _maxval = max_rec(self, left + 1, right); 
    return self->arr[left] > _maxval ? self->arr[left] : _maxval;
}

int max(Object* self) {
    return max_rec(self, 0, self->size);
}

// 총 합계 재귀 알고리즘
int sum_rec(Object* self, int left, int right) {
    if (left > right) return 0; // 더 이상 더해지지 않도록 0 리턴
    
    // 재귀적으로 합계 계산
    return self->arr[left] + sum_rec(self, left + 1, right);
}

int sum(Object* self) {
    return sum_rec(self, 0, self->size);
}

 

같은 일을 하는 코드지만 뭔가 좀 더 복잡해 진 것 같다.

하지만 사실 더 간단해졌다.

 

왜냐하면 문제가 작아졌기 때문이다.

// 최솟값 재귀 알고리즘
int min_rec(Object* self, int left, int right) {
    if (left > right) return MAX_VALUE; // 최댓값 리턴
    
    // 재귀적으로 left 이후의 최솟값 가져오기
    int _minval = min_rec(self, left + 1, right); 
    return self->arr[left] < _minval ? self->arr[left] : _minval;
}

탈출 조건에 이를 때 까지 재귀 알고리즘은 자기 자신을 계속 호출하는 식으로 동작한다.

따라서 문제는 개별 함수 스택 프레임 단위로 쪼개진다.

 

다른거 다 치우고 마지막 return만 보자.

return self->arr[left] < _minval ? self->arr[left] : _minval;

현재 (left) 값과 여태까지의 최솟값 _minval 과의 비교하여 작은 쪽을 리턴하도록 작성되어 있다.

굳이 현재 값이 뭐니 하면서 비교하고 바꿔치고 할 필요 없이, 그냥 둘 중 작은 놈을 고른다.

탈출 조건에 도달 했을 때, 스택 프레임들이 정리되면서 최솟값들이 계속 리턴되어 올라올 거고,

그럼 min()에서 결국 최솟값이 리턴된다.

 

 

이렇듯, 재귀는 문제를 쪼갤 수 있다.

따라서 복잡한 문제도 더욱 쉽게 접근하여 해결 할 수 있을 것이다.

재귀적으로 생각하는 훈련을 해두는 것이 좋겠다.

 

 

그러므로 결론: 객기부리지 말자.