C++ 재귀 호출로 배열의 최솟값과 최댓값 찾기

정수 배열 Arr[]가 입력으로 주어졌을 때, 재귀(순환 호출) 방식을 사용해 배열 안에서 최댓값과 최솟값을 찾는 것이 이 글의 목표입니다.

재귀로 문제를 해결하기 때문에 배열을 계속 탐색하다가 길이가 1이 되는 순간 A[0]을 반환하는데, 이것이 곧 기저 사례(base case)입니다. 그 외의 경우에는 현재 요소를 지금까지 구한 최솟값 또는 최댓값과 비교하고, 남은 요소들을 대상으로 재귀 호출을 이어가며 값을 갱신해 나갑니다.

입출력 시나리오 살펴보기

입력 − Arr = {12, 67, 99, 76, 32};

출력 − 배열의 최댓값 : 99

설명 − 모든 요소 가운데 99가 가장 큰 값입니다.

입력 − Arr = {1, 0, -99, 9, 3};

출력 − 배열의 최솟값 : -99

설명 − 모든 요소 가운데 -99가 가장 작은 값입니다.

프로그램에 적용된 접근 방식

최솟값 찾기

배열 Arr[]를 입력으로 받습니다.
함수 recforMin(int arr[], int len)는 입력 배열과 그 길이를 인자로 받아, 재귀 호출을 통해 배열의 최솟값을 반환합니다.
정수형 변수 minimum을 선언합니다.
현재 인덱스 len이 1이면 minimum = arr[0]으로 설정한 뒤 minimum을 반환합니다.
그렇지 않으면 minimum을 arr[len]과 recforMin(arr, len-1) 중 더 작은 값으로 설정하여 반환합니다.
모든 재귀 호출이 끝나면 최종적으로 최솟값이 반환됩니다.
main 함수 안에서 결과를 출력합니다.

최댓값 찾기

배열 Arr[]를 입력으로 받습니다.
함수 recforMax(int arr[], int len)는 입력 배열과 그 길이를 인자로 받아, 재귀 호출을 통해 배열의 최댓값을 반환합니다.
정수형 변수 maximum을 선언합니다.
현재 인덱스 len이 1이면 maximum = arr[0]으로 설정한 뒤 maximum을 반환합니다.
그렇지 않으면 maximum을 arr[len]과 recforMax(arr, len-1) 중 더 큰 값으로 설정하여 반환합니다.
모든 재귀 호출이 끝나면 최종적으로 최댓값이 반환됩니다.
main 함수 안에서 결과를 출력합니다.

재귀로 최솟값 구하기

예제 코드

#include <iostream>
using namespace std;
int recforMin(int arr[], int len){
    int minimum;
    if (len == 1){
        minimum = arr[0];
        return minimum;
    }
    else{
        return minimum = arr[len] < recforMin(arr, len-1) ? arr[len] : recforMin(arr, len-1);
    }
}
int main(){
    int Arr[] = {-89, 98, 76, 32, 21, 35, 100};
    int length = sizeof(Arr)/sizeof(Arr[0]);
    cout << "Minimum in the array :" << recforMin(Arr, length-1);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Minimum in the array :-89

재귀로 최댓값 구하기

예제 코드

#include <iostream>
using namespace std;
int recforMax(int arr[], int len){
    int maximum;
    if (len == 1){
        maximum = arr[0];
        return maximum;
    }
    else{
        return maximum = arr[len] > recforMax(arr, len-1) ? arr[len] : recforMax(arr, len-1);
    }
}
int main(){
    int Arr[] = {-89, 98, 76, 32, 21, 35, 100};
    int length = sizeof(Arr)/sizeof(Arr[0]);
    cout << "Maximum in the array :" << recforMax(Arr, length-1);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Maximum in the array :100

동작 원리와 시간 복잡도

이 풀이의 핵심은 "마지막 요소 하나"와 "나머지 요소들의 최솟값(또는 최댓값)"을 비교하는 것입니다. 함수가 자기 자신을 계속 호출하다가 len == 1에 도달하면 첫 번째 요소를 반환하고, 호출 스택을 거슬러 올라오면서 각 단계마다 비교 결과를 되돌려줍니다.

배열의 모든 요소를 한 번씩 비교하므로 시간 복잡도는 O(n)이며, 재귀 호출 깊이만큼 스택 메모리를 사용하므로 공간 복잡도 역시 O(n)입니다. 따라서 배열의 크기가 매우 클 경우에는 스택 오버플로우가 발생하지 않도록 주의해야 합니다.

참고: 함수 내부에서 arr[len]에 직접 접근하므로, main에서는 반드시 length - 1(유효한 마지막 인덱스)을 인자로 넘겨야 배열 범위를 벗어나는 접근을 피할 수 있습니다.