나는 재귀를 잘 사용하지 않는다.
함수 호출하는 코스트가 큰 탓도 있고,
무엇보다도 반복문으로 간단하게 표현 가능한 로직을 굳이 재귀로 표현할 필요를 못 느끼기 때문이기도 하다.
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()에서 결국 최솟값이 리턴된다.
이렇듯, 재귀는 문제를 쪼갤 수 있다.
따라서 복잡한 문제도 더욱 쉽게 접근하여 해결 할 수 있을 것이다.
재귀적으로 생각하는 훈련을 해두는 것이 좋겠다.
그러므로 결론: 객기부리지 말자.