C++で再帰を使って配列の最小値・最大値を求める方法

整数型の配列 Arr[] が入力として与えられます。この記事では、再帰(リカーシブ)処理を用いて、配列の中から最大要素と最小要素を見つける方法を解説します。

再帰を利用する場合、配列の長さ(len)が 1 になるまで再帰呼び出しを繰り返し、len == 1 になった時点で arr[0] を返します。これがベースケース(基本ケース)です。それ以外の場合は、現在の要素とこれまでに求めた最小値(または最大値)を比較し、より小さい(または大きい)方の値を返しながら、残りの要素へ再帰的に処理を進めていきます。

入出力シナリオの例

入力 − 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 = min(arr[len], recforMin(arr, len-1)) として計算し、その値を返します。
• 最終的に、配列全体の最小要素が返されます。
• main 関数内で結果を出力します。

最大値を求める場合

• 配列 Arr[] を入力として受け取ります。
• 関数 recforMax(int arr[], int len) は、入力配列とその長さを受け取り、再帰によって配列内の最大値を返します。
• 整数変数 maximum を用意します。
• 現在のインデックス len が 1 の場合は、maximum = arr[0] として maximum を返します(ベースケース)。
• それ以外の場合は、maximum = max(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);
    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);
    return 0;
}

実行結果

Maximum in the array :100

まとめ

このように、再帰を使えばループ処理を書かずとも、配列の末尾から順に要素を比較していくことで最小値・最大値を求められます。ベースケース(len == 1)を正しく設定することが、再帰プログラムを安全かつ正確に動作させるポイントです。なお、要素数が非常に多い配列では再帰の深さが増えるため、スタックオーバーフローに注意が必要です。