【C言語】再帰を使って配列が回文かどうかを判定するプログラム

配列 arr[n](n は配列のサイズ)が与えられたとき、再帰を用いてその配列が回文かどうかを判定するのが本記事のテーマです。回文とは、前から読んでも後ろから読んでも同じになる並びのことで、「MADAM」や「NAMAN」などが代表的な例です。

配列が回文かどうかを調べるには、先頭と末尾から順に要素を比較していきます。

再帰的なアプローチでも同様に、start と end の値を更新しながら比較を続けます。start と end が交差(すれ違う)すれば回文と判定でき、途中で要素が一致しなかった場合はそこで処理を打ち切り、false を返します。

入力例と出力例

入力: arr[] = { 2, 3, 4, 3, 2}
出力: はい、この配列は回文です
説明: 先頭から見た並び (2, 3, 4, 3, 2) と末尾から見た並び (2, 3, 4, 3, 2) が同一であるため。

入力: arr[] = {1, 2, 3, 4}
出力: いいえ、この配列は回文ではありません
説明: 先頭から見た並び (1, 2, 3, 4) と末尾から見た並び (4, 3, 2, 1) が同一ではないため。

アプローチの考え方

今回採用するアプローチでは、以下のステップを再帰的に実行します。

• arr[start] と arr[end] が等しく、かつ start < end であるかを確認する
• start を 1 増やし、end を 1 減らす
• ステップ 1 に戻る

アルゴリズム

開始
関数 int palindrome(int arr[], int start, int end)
    ステップ 1 -> もし start >= end ならば、
        1 を返す
    ステップ 2 -> もし arr[start] == arr[end] ならば、
        palindrome(arr, start + 1, end - 1) を返す
    ステップ 3 -> それ以外の場合 {
        0 を返す
関数 int main()
        ステップ 1 -> 配列 arr[] を宣言・初期化する
        ステップ 2 -> n = sizeof(arr) / sizeof(arr[0]) を宣言・初期化する
        ステップ 3 -> もし palindrome(arr, 0, n - 1) == 1 ならば、
            「Yes, the array is Palindrome」と出力する
        ステップ 4 -> それ以外の場合
            「No, the array is not Palindrome」と出力する
終了

C言語での実装例

#include <stdio.h>
// 回文であれば 1 を、そうでなければ 0 を返す再帰関数
int palindrome(int arr[], int start, int end) {
   // ベースケース
   if (start >= end) {
      return 1;
   }
   if (arr[start] == arr[end]) {
      return palindrome(arr, start + 1, end - 1);
   } else {
      return 0;
   }
}
// ドライバーコード
int main() {
   int arr[] = { 1, 2, 0, 2, 1 };
   int n = sizeof(arr) / sizeof(arr[0]);
   if (palindrome(arr, 0, n - 1) == 1)
      printf("Yes, the array is Palindrome\n");
   else
      printf("No, the array is not Palindrome\n");
   return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Yes, the array is Palindrome

計算量について

この再帰アプローチでは、配列の先頭と末尾を同時に比較していくため、比較回数はおよそ n/2 回となります。したがって時間計算量は O(n)、再帰呼び出しによるスタック領域も O(n) 必要になります。ループを使った反復処理に比べコードは簡潔になりますが、大きな配列を扱う場合はスタックオーバーフローに注意が必要です。